class53单调栈-下

除了单调栈最经典的用法之外，在很多问题里单调栈还可以 维持求解答案的可能性

  1. 单调栈里所有的对象按照规定好的单调性来组织（小压大等）
  2. 当某个对象进入单调栈时，会从栈顶开始淘汰单调栈内对后续求解答案没有帮助的对象
  3. 每个对象从栈顶弹出的时候结算当前对象参与的答案，随后这个对象不再参与后续求解答案的过程

题目1

测试链接：962. 最大宽度坡

做法：

  1. 维护一个单调栈，存放答案可能的左边界，用小压大实现
  2. 从后往前遍历数组（int j = n - 1），假定当前位置为答案的右边界，依次与栈顶元素比较，如果满足宽度坡，记录答案，淘汰栈顶元素，继续与栈中下一个元素比较，如果不满足宽度坡，j--,重复上述操作

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public static int MAXN = 50001;
    public static int[] statck = new int[MAXN];
    public static int r;
    public int maxWidthRamp(int[] arr) {
        statck[0] = 0;
        r = 1;
        int n = arr.length;
        for(int i = 1; i < n;i++){
            while(arr[statck[r-1]] > arr[i]){
                statck[r++] = i;
            }
        }
        int ans = 0;
        for(int j = n - 1;j > 0;j--){
            while(r > 0 && arr[statck[r-1]] <= arr[j]){
                ans = Math.max(ans,j - statck[--r]);
            }
        }
        return ans;
    }
}

题目2

题目链接：316. 去除重复字母

做法

  1. 维护一个单调栈，遵循大压小，维护一个词频数组，记录个字符出现的次数，维护一个enter数组，记录字符是否在栈中
  2. 遍历字符串，如果栈中有元素，且栈顶元素大于当前元素且栈顶元素词频不为0,弹出栈顶元素，继续判断直至栈顶元素小于当前元素，将当前元素入栈，词频减1,入栈数组置为true

代码

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 {
    public static int MAXN = 26;
    public static int[] cnts = new int[MAXN]; // 统计词频
    public static boolean[] enter = new boolean[MAXN];//是否进栈
    public static char[] statck = new char[MAXN];
    public static int r;//栈大小
    public String removeDuplicateLetters(String str) {
        r = 0;
        char[] s = str.toCharArray();
        Arrays.fill(cnts,0);
        Arrays.fill(enter,false);
        //统计词频
        for(char cur : s){
            cnts[cur - 'a']++;
        }
        for(char cur : s){
            //当前字符未进栈
            if(!enter[cur - 'a']){
                while(r > 0 && statck[r-1] > cur && cnts[statck[r-1] - 'a'] != 0){
                    enter[statck[r-1] - 'a'] = false;
                    r--;
                }
                statck[r++] = cur;
                enter[cur - 'a'] = true;
            }
            //当前字符词频减少1
            cnts[cur - 'a']--;
        }
        return String.valueOf(statck,0,r);
    }
}

题目3

题目链接：大雨吃小鱼牛客题霸牛客网

做法

  1. **维护一个单调栈，遵循小压大，栈中存储 **(鱼的体积, 吞并所需操作次数)
  2. 从右向左遍历数组，对每个元素：
    • 弹出所有比当前鱼小的栈顶元素
    • 更新当前鱼的吞并次数：curTurns = max(curTurns + 1, 弹出元素的吞并次数)
    • 将当前鱼及其吞并次数压入栈
  3. 全局最大吞并次数即为答案

代码

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
import java.util.*;
​
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int MAXN = 100001;
    public static int[] arr = new int[MAXN];
    public static int[][] statck = new int[MAXN][2];
    public static int r;
    public static int n;
    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;
            }
            out.println(turns());
        }
        out.flush();
        out.close();
        br.close();
    }
    public static int turns() {
        r = 0;
        int ans = 0;
        for (int i = n - 1, curTurns; i >= 0; i--) {
            curTurns = 0;
            while (r > 0 && statck[r - 1][0] < arr[i]) {
                curTurns = Math.max(curTurns + 1, statck[--r][1]);
            }
            statck[r][0] = arr[i];
            statck[r++][1] = curTurns;
            ans = Math.max(ans, curTurns);
        }
        return ans;
    }
}

题目4

链接：1504. 统计全 1 子矩形

做法

  1. **将二维问题转换为一维问题，对于每一行 **i，我们维护一个 height 数组，其中 height[j] 表示从当前行向上连续的 1 的个数（即以第 i 行为底，第 j 列的高度）

  2. 对每行的高度数组，统计以该行为底的全 1 子矩形数量

    • 左边界：栈中前一个元素（栈空为-1）
    • 右边界：当前元素k
    • 长度:k - left - 1;
    • 有效范围：(height[cur] - bottom)，其中 bottom 是左右边界中的较大值,在这个范围内，可以形成 (height[cur] - bottom) * len * (len + 1) / 2 个子矩形。

    为什么是 len \* (len + 1) / 2？ **因为在长度为 **len 的连续区间中，有 len 个长度为 1 的子区间，len-1 个长度为 2 的子区间，…，1 个长度为 len 的子区间，总和为 len * (len + 1) / 2。

代码

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
class Solution {
    public static int MAXN = 151;
    public static int[] height = new int[MAXN];
    public static int[] stack = new int[MAXN];
    public static int r;
    public int numSubmat(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        Arrays.fill(height, 0, m, 0);
        int ans = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                //对于每一行i，维护一个height数组，height[j]表示当前行向上连续1的个数
                height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;
            }
            //每行数据累加
            ans += countFromBottom(m);
        }
        return ans;
    }
    public static int countFromBottom(int m){
        r = 0;
        int ans = 0;
        //遍历height数组
        for(int k = 0,left,len,bottom;k < m;k++){
            //找到右边界出栈（小于等于栈顶）
            while(r > 0 && height[stack[r-1]] >= height[k]){
                int cur = stack[--r];
                if(height[cur] > height[k]){
                    left = r == 0 ? -1 : stack[r-1];//左边界
                    len = k - left - 1;//宽度
                    bottom = Math.max(left == -1 ? 0 : height[left],height[k]);//下界
                    ans += (height[cur] - bottom) * (len*(len+1)) / 2;
                }
            }
            stack[r++] = k;
        }
        //处理栈中剩余元素
        while(r > 0){
            int cur = stack[--r];
            int left = r == 0 ? -1 : stack[r-1];
            int len = m - left - 1;
            int bottom = (left == -1 ? 0 : height[left]);
            ans +=(height[cur] -  bottom) * (len*(len+1)) / 2;
        }
        return ans;
    }
}