单调栈

发表于 更新于 分类于 阅读次数：

基础

单调栈分为单调递增，单调递减

  • 递增栈：
    • 栈内元素从栈底到栈顶递增。
    • 用于寻找 下一个更小元素。
  • 递减栈：
    • 栈内元素从栈底到栈顶递减。
    • 用于寻找 下一个更大元素。

👉 核心模式就是：

1
2
3
4
5
6
7
for (...) {
    while (!stack.isEmpty() && 当前元素和栈顶元素满足某条件) {
        // 处理逻辑：清算旧账
        stack.pop();
    }
    stack.push(当前元素/下标);
}

每日温度[🔥59]

题目：找出每个元素多少index后会出现比他大的元素

思路：

  1. 维护一个单调递减栈，存的是index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        //维护一个单调递增栈，用来存放已经遍历过的元素，然后就可以与当前元素进行一个比较
        //该题是一个单调递减栈，栈顶 --> 栈低 是递增的
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            //队列不为空 然后如果当前元素大于那个已经遍历过的元素，那就去清理旧账 
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int curIndex = stack.pop();
                //求的是间隔
                res[curIndex] = i - curIndex;
            }
            stack.add(i);
        }
        return res;
    }
}

时间复杂度：ON

空间复杂度：ON

84. 柱状图中最大的矩形[28]

思路：

  1. 本质上还是接雨水，理解两个点： 1. 面积等于高度 * 宽度，所以对于任何一个柱子，都要看看往左右两边伸展的最大宽度是多少，使用单调栈 2. 栈有两个语义，栈[-2] 是栈[-1]的左边界，出栈操作时，表示栈[-1] > 当前元素，这样就为栈顶元素确定了两个边界。
  2. 这里解释一下，range 为什么是 range = i - leftIndex - 1; i 即右边第一个比 h(mid) 小的柱子位置，而leftindex 即左边第一个比它小的柱子（这个值很容易，根据单调栈特性，我们就可以直接peek()出来）
  3. 那么当前mid柱子 可扩展的范围 也就是 最右 - 最左 - 1 这里的 - 1就是要把最右最左给排除掉
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    //以 heights[i]为高的 矩形面积有多大
    //heights[i] 为基准
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] newHeights = new int[n+2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        System.arraycopy(heights, 0, newHeights, 1 , n);
        //System.out.println(Arrays.toString(newHeights));

        Stack<Integer> s = new Stack();
        s.add(0);
        int res = 0;
        for(int i = 0; i < newHeights.length; i++){
            while(!s.isEmpty() && newHeights[i] < newHeights[s.peek()]){
                int midIndex = s.pop();
                if(s.isEmpty()){
                    break;
                }
                int leftIndex = s.peek();
                //以h(mid)为高度 左右扩展的范围
                // leftIndex midIndex .... i
                int range = i - leftIndex - 1;
                res = Math.max(res, newHeights[midIndex] * range);
            }
            s.add(i);
        }
        return res;
    }
}

最大矩形[27]

思路：

  1. 先做84题，是它的父问题。就是把它切 m(martix.length )个 84题问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    int res = 0;
    public int maximalRectangle(char[][] matrix) {
        int[][] t = new int[matrix.length][matrix[0].length + 2];
        for(int i = 0; i < t.length; i++){
            t[i][0] = 0; 
            t[i][t[0].length - 1] = 0; 
        }
        // 转换成 84题那种柱状图
        for(int i = 0; i < t.length; i++){
            for(int j = 1; j < t[0].length - 1; j++){
                if(matrix[i][j - 1] == '1'){
                    t[i][j] = 1;
                    //当前 位置为 1时，才能有高度
                    if(i > 0) t[i][j] += t[i - 1][j];
                }
                else t[i][j] = 0;
                
            }
        }
        // for(int [] tt: t){
        //     System.out.println(Arrays.toString(tt));
        // }

        for(int[] tt: t){
            f1(tt);
        }
        return res;        
    }
    public void f1(int []hegihts){
        Stack<Integer> s = new Stack();
        s.add(0);
        for(int i = 1; i < hegihts.length; i++){
            while(!s.isEmpty() && hegihts[s.peek()] > hegihts[i]){
                int midIndex = s.pop();
                if(s.isEmpty()){
                    break;
                }
                int leftIndex = s.peek();
                res = Math.max(res, hegihts[midIndex] * (i - leftIndex - 1));
            }
            s.add(i);
        }
    }
}

去除重复字母