栈——算法专项刷题（六）

﹏ヽ暗。殇╰゛Y 2024-03-31 11:44 76阅读 0赞

### 六、栈 ###

#### 6.1后缀表达式 ####

[原题链接][Link 1]

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

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

**说明：**

*  整数除法只保留整数部分。
 *  给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 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<Integer> 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小行星碰撞 ####

[原题链接][Link 3]

给定一个整数数组 `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<Integer> 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){
        
                  //栈顶元素小于 0
                  stack.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<Integer> stack = new ArrayDeque<Integer>();
            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 每日温度 ####

[每日温度][Link 4]

请根据每日 气温 列表 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<Integer> 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 直方图最大矩形面积 ####

[原题链接][Link 5]

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

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

![在这里插入图片描述][675b69ae16bd482996548258d49139a7.png]

*  输入：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，那么再进行双指针左右扩展也不能大于max
                if(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矩阵中的最大矩形 ####

[原题链接][Link 6]

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

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

![在这里插入图片描述][527caa02f6fc414089dd32b0bd794728.png]

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

**提示：**

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

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

详细参考leetcode官方题解[链接][Link 7]

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<Integer> stack = new ArrayDeque<Integer>();
                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;
        }
    }

[Link 1]: https://leetcode.cn/problems/8Zf90G/
[Link 2]: https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437
[Link 3]: https://leetcode.cn/problems/XagZNi/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=4kehfu1
[Link 4]: https://leetcode.cn/problems/iIQa4I/
[Link 5]: https://leetcode.cn/problems/0ynMMM/
[675b69ae16bd482996548258d49139a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/460bfc6268064674934d9f65b55542e5.png
[Link 6]: https://leetcode.cn/problems/PLYXKQ/
[527caa02f6fc414089dd32b0bd794728.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/0e6b13bc23ae4ae996600df3a8bc97db.png
[Link 7]: https://leetcode.cn/problems/PLYXKQ/solution/ju-zhen-zhong-zui-da-de-ju-xing-by-leetc-pjc7/