六、栈

6.1后缀表达式

原题链接

根据 逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

• 输入：tokens = [“2”,“1”,“+”,“3”,“*”]

• 输出：9

• 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

提示：

1 <= tokens.length <= 10^4
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

思路：栈的基本使用，是数值就压栈，是运算符就弹出两个数值

注意点：数值可能为负，如果字符串第一个字符是 - 可能是负数也可能是 减法运算，通过字符串长度进行判断

class Solution {public int evalRPN(String[] tokens) {Stack stack = new Stack<>();int n = tokens.length;for (int i = 0; i < n; i++) {char c = tokens[i].charAt(0);if(c >= '0' && c <='9' || (c == '-' && tokens[i].length() > 1)){stack.push(Integer.valueOf(tokens[i]));}else {int num1 = stack.pop();int num2 = stack.pop();if (c == '+') {stack.push(num2 + num1);}else if(c == '-'){stack.push(num2 - num1);}else if( c == '/'){int num = num2 / num1;stack.push(num);}else{int num = num2 * num1;stack.push(num);}}}return stack.pop();}
}

6.2小行星碰撞

原题链接

给定一个整数数组 asteroids，表示在同一行的小行星。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

• 输入：asteroids = [5,10,-5]

• 输出：[5,10]

• 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

提示：

• 2 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

解法一：栈

思路： 使用栈来模拟碰撞可能，只有一个正数 一个负数 这种顺序才能发生碰撞

注意点： 当前数值为负可以一直和栈中小的正数碰撞

class Solution {public int[] asteroidCollision(int[] asteroids) {int n = asteroids.length;Stack stack = new Stack<>();for (int i = 0; i < n; i++) {// 栈为空或者 当前值大于 0 压栈if(stack.isEmpty() || asteroids[i] > 0){stack.push(asteroids[i]);continue;}int cur = - asteroids[i];// 栈顶的值为正数，大于当前值 消除while(!stack.isEmpty() && stack.peek() > 0 && cur > stack.peek()){stack.pop();}// 栈不为空if(!stack.isEmpty()){// 相等 消除栈顶元素if(stack.peek() == cur) {stack.pop();}else if(stack.peek() < 0){//栈顶元素小于 0stack.push(asteroids[i]);}}else{stack.push(asteroids[i]);}}int size = stack.size();int[] ans = new int[size];for (int i = size - 1; i >= 0; i--) {ans[i] = stack.pop();}return ans;}
}

解法二：

思路： 模拟碰撞，使用一个alive标识表示当前小行星是否存在，当当前小行星为负、存在并且栈顶元素是大于0 且 小于 -aster 栈顶小行星爆炸

注意： 边界情况

class Solution {public int[] asteroidCollision(int[] asteroids) {Deque stack = new ArrayDeque();for (int aster : asteroids) {boolean alive = true;while (alive && aster < 0 && !stack.isEmpty() && stack.peek() > 0) {alive = stack.peek() < -aster; // aster 是否存在if (stack.peek() <= -aster) {  // 栈顶小行星爆炸stack.pop();}}if (alive) {stack.push(aster);}}int size = stack.size();int[] ans = new int[size];for (int i = size - 1; i >= 0; i--) {ans[i] = stack.pop();}return ans;}
}

6.3 每日温度

每日温度

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

• 输入: temperatures = [73,74,75,71,69,72,76,73]
• 输出: [1,1,4,2,1,1,0,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

思路： 单调栈，在栈中存数组下标，如果当前温度 > 栈顶下标对应的温度，弹栈并保存栈顶下标对应的 之后升温天数

注意点： 使用栈记录温度会不知道具体下标，因此直接 用下标代替栈

class Solution {public int[] dailyTemperatures(int[] temperatures) {Stack stack = new Stack<>();int n = temperatures.length;int[] res = new int[n];for (int i = 0; i < n; i++) {while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){res[stack.peek()] = i - stack.peek();stack.pop();}stack.push(i);}return res;}
}

6.4 直方图最大矩形面积

原题链接

给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

• 输入：heights = [2,1,5,6,2,3]
• 输出：10
• 解释：最大的矩形为图中红色区域，面积为 10

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

思路： 对每个位置的数组值，如果左右指针指向的数组值 大于此位置的值，左指针向左移动，右指针向右移动

注意点： 在进行双指针移动前需要判断 是否需要进行移动，如果当前数组值 * 数组总长度 都不能大于 max 那么双指针移动无意义，直接跳过此轮循环

class Solution {public int largestRectangleArea(int[] heights) {int max = 0;int left = 0;int right = 0;for(int i = 0; i < heights.length;i++){left = i -1;right = i+1;// 如果当前值 乘于 整个数组长度 都不能大于max，那么再进行双指针左右扩展也不能大于maxif(heights.length * heights[i] > max){while (left >=0 && heights[left] >= heights[i]){left--;}while(right < heights.length && heights[right] >= heights[i]){right++;}max = Math.max(max, (right - left - 1) * heights[i]);}}return max;}
}

6.5矩阵中的最大矩形

原题链接

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意： 此题 matrix 输入格式为一维 01 字符串数组。

• 输入：matrix = [“10100”,“10111”,“11111”,“10010”]
• 输出：6
• 解释：最大矩形如上图所示。

提示：

• rows == matrix.length
• cols == matrix[0].length
• 0 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

思路：基本思路 是先遍历一遍数组，将每一行 所有元素的左侧连续1的个数进行统计，然后就是确定高度 找最大的宽度进行计算

详细参考leetcode官方题解链接

class Solution {public int maximalRectangle(String[] matrix) {int m = matrix.length;if (m == 0) {return 0;}int n = matrix[0].length();int[][] left = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i].charAt(j) == '1') {// 统计每一行 连续 1的个数left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;}}}int ret = 0;for (int j = 0; j < n; j++) { int[] up = new int[m];int[] down = new int[m];Deque stack = new ArrayDeque();for (int i = 0; i < m; i++) {while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {stack.pop();}up[i] = stack.isEmpty() ? -1 : stack.peek();stack.push(i);}stack.clear();for (int i = m - 1; i >= 0; i--) {while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {stack.pop();}down[i] = stack.isEmpty() ? m : stack.peek();stack.push(i);}for (int i = 0; i < m; i++) {int height = down[i] - up[i] - 1;int area = height * left[i][j];ret = Math.max(ret, area);}}return ret;}
}