class52单调栈-上

描述：

单调栈最经典的用法是解决如下问题：

每个位置都求：

0）当前位置的 左侧比当前位置的数字小，且距离最近的位置 在哪

1）当前位置的 右侧比当前位[[置的数字小，]]且距离最近的位置 在哪

或者

每个位置都求：

0）当前位置的 左侧比当前位置的数字大，且距离最近的位置 在哪

1）当前位置的 右侧比当前位置的数字大，且距离最近的位置 在哪

用单调栈的方式可以做到：求解过程中，单调栈所有调整的总代价为O(n)，单次操作的均摊代价为O(1)

做法：

  1. 相较于无重复值的数组而言，有重复值的数组只需要在最后的答案上修正即可
  2. 以第一种情况举例，自己用数组实现一个栈，里面放下标（既可以知道值的位置，也可以知道值的大小）严格遵循大压小，第二种情况则遵循小压大
  3. 遍历阶段遍历整个数组，当遍历到i位置时，当栈中还有元素且arr[statck[r-1]] <= arr[i],即栈顶元素对应数组的值小于i位置对应数组的值，弹出，记录答案，谁让它弹出的谁就是右边最小，如果此时栈里还有元素，下一个即为左边最小，没有元素则为-1
  4. 清算阶段当遍历完数组后，栈里仍有元素，此时没有右边最小，当前元素下面还有元素时，左侧最小为下面元素。栈底元素既没有左侧最小也没有右侧最小
  5. 修正阶段:，从后往前遍历，最后一个无需遍历，从n-2开始，如果arr[ans[i][1]] == arr[i]，即i位置的值等于其右侧最小对应元素的值，把其更新为右侧最小对应元素的值的右侧最小ans[i][1] = ans[ans[i][1]][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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package com.study.class52;
​
import java.io.*;
​
public class LeftRightLess {
    public static int MAXN = 1000001;
    public static int[] arr = new int[MAXN];
    public static int[] statck =  new int[MAXN];
    public static int[][] ans  = new int[MAXN][2];
    public static int n,r;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n = (int)in.nval;
            for(int i=0;i<n;i++){
                in.nextToken();
                arr[i] = (int)in.nval;
            }
            compute();
            for(int i=0;i<n;i++){
                System.out.println(ans[i][0] + " " + ans[i][1]);
            }
        }
        out.close();
        out.flush();
        br.close();
    }
    public static void compute(){
        //r用来维护栈
        r = 0;
        //遍历阶段
        for(int i = 0,cur;i < n;i++){
            while(r > 0 && arr[statck[r-1]] <= arr[i]){
                cur = statck[--r];
                ans[cur][0] = r > 0 ? statck[r-1] : -1;
                ans[cur][1] = i;
            }
            statck[r++] = i;
        }
        //清算阶段，将栈内剩余元素全部弹出
        while(r > 0){
            int cur =  statck[--r];
            ans[cur][0] = r > 0 ? statck[r-1] : -1;
            ans[cur][1] = -1;
        }
        //修正阶段，从后往前修正
        for(int i = n - 1;i >= 0;i--){
            while(ans[i][1] != -1 && arr[ans[i][1]] == arr[i]){
                ans[i][1] = ans[ans[i][1]][1];
            }
        }
​
    }
}
​

题目2

测试链接：739. 每日温度 - 力扣（LeetCode）

做法：

  1. 找出右侧最大，即第二种情况，遵循小压大，遍历整个数组，如果nums[statck[r-1]] < nums[i],弹出元素，记录答案
  2. 值得注意的是，此题遇到重复值不用弹出，仍将重复值压入栈，这几个重复值共用一个右侧最大，其实弹出也行，依照上题修正即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public static int MAXN = 100001;
    public static int[] statck = new int[MAXN];
    public static int r;
    public int[] dailyTemperatures(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        r = 0;
        for(int i = 0,cur;i < n;i++){
            //r>0限制栈中仍有元素
            while(r > 0 && nums[statck[r-1]] < nums[i]){
                 cur = statck[--r];
                 ans[cur] = i - cur;
            }
            statck[r++] = i;
        }
        return ans;
    }
}

题目3

链接：907. 子数组的最小值之和 - 力扣（LeetCode）

做法

  1. 我们不去计算每个子数组的最小值，而是计算每个元素对于答案的贡献。对于元素arr[i]，只有当它是某些子数组的最小值时，它才会为答案做贡献，贡献值为以它为最小值的子数组的个数*arr[i]
  2. 维护一个单调栈，严格遵循大压小，当arr[stack[r-1]] >= arr[i]，说明找到了栈顶元素的右边界，只限制小于会多计算字数组\
  3. 弹出栈顶元素，计算其贡献值
  4. 左边界就是栈中下一个元素（或-1）
  5. 处理完所有元素后，清理栈中剩余元素

代码

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
class Solution {
    public static int MOD = 1000000007;
    public static int MAXN = 30001;
    public static int[] stack = new int[MAXN];
    public static int r;
​
    public int sumSubarrayMins(int[] arr) {
      r = 0;
      int left;
      long ans = 0;
      for(int i = 0,cur;i < arr.length;i++){
        while(r > 0 && arr[stack[r-1]] >= arr[i]){
             cur = stack[--r];
             left = r == 0 ? -1 :stack[r-1];
             //(long)(cur - left)使得后续运算都在long环境下执行
             //(ans+当前答案)%mod，防止ans过大，加上当前答案超过MOD
             ans = (ans + (long)(cur - left)*(i - cur) * arr[cur])%MOD;
        }
        stack[r++] = i;
      }
      while(r > 0){
        int cur = stack[--r];
        left = r == 0 ? -1 :stack[r-1];
        ans = (ans + (long)(cur - left)*(arr.length - cur) * arr[cur])%MOD;
      }
      return (int)ans;
    }
}

题目4

链接：84. 柱状图中最大的矩形 - 力扣（LeetCode）

做法

  1. 求矩形的最大值，我们只需比较每个元素*以这个元素为起点向左右延伸的最远距离即可
  2. 维护一个单调栈，严格遵循大压小，当heights[stack[r-1]] >= heights[i],即栈顶元素大于等于当前元素时，弹出，如果栈中还有元素，左边界即为栈中下一个元素，否则为-1,右边界即i,面积为(i - left - 1)*heights[cur]
  3. 之所以大于等于的时候弹出，而不是等于，与上题同理，后来的元素可以继承当前栈顶元素未达到的边界
  4. ![image-20251217203605950](file:///C:/Users/Peter/AppData/Roaming/Typora/typora-user-images/image-20251217203605950.png?lastModify=1773844252)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public static int MAXN = 100001;
    public static int[] stack = new int[MAXN];
    public static int r;
    public int largestRectangleArea(int[] heights) {
        r = 0;
        int ans = 0;
        int cur,left;
        for(int i = 0;i < heights.length;i++){
           while(r > 0 && heights[stack[r-1]] >= heights[i]){
            cur = stack[--r];
            left = r == 0 ? -1 : stack[r-1];
            ans = Math.max(ans,(i - left - 1)*heights[cur]);
           }
           stack[r++] = i;
        }
        while(r > 0){
            cur = stack[--r];
            left = r == 0 ? -1 : stack[r-1];
            ans = Math.max(ans,(heights.length - left - 1)*heights[cur]);
        }
        return ans;
    }
}

题目5

题目链接：85. 最大矩形 - 力扣（LeetCode）

做法：

  1. 本题做法与上题高度一致，遍历二维数组，当我们来到第i行的时候，要求以第i行为底，构造一系列矩形，题目要求就和上题一样

代码

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
class Solution {
    public static int MAXN = 201;
    public static int[] height = new int[MAXN];
    public static int[] statck = new int[MAXN];
    public static int r;
​
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int ans = 0;
        Arrays.fill(height, 0, m, 0);
        for (int i = 0; i < n; i++) {
            // 来到i行，长方形一定要以i行做底！
            // 加工高度数组(压缩数组)
            for (int j = 0; j < m; j++) {
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            }
            ans = Math.max(ans, largestRectangleArea(m));
        }
        return ans;
    }
​
    public static int largestRectangleArea(int m) {
        r = 0;
        int ans = 0;
        int cur, left;
        for (int i = 0; i < m; i++) {
            while (r > 0 && height[statck[r - 1]] >= height[i]) {
                cur = statck[--r];
                left = r == 0 ? -1 : statck[r - 1];
                ans = Math.max(ans, (i - left - 1) * height[cur]);
            }
            statck[r++] = i;
        }
        while (r > 0) {
            cur = statck[--r];
            left = r == 0 ? -1 : statck[r - 1];
            ans = Math.max(ans, (m - left - 1) * height[cur]);
        }
        return ans;
    }
}