单调栈-下
基本介绍
除了单调栈最经典的用法之外，在很多问题里单调栈还可以维持求解答案的可能性
（1）单调栈里的所有对象按照规定好的单调性来组织
（2）当某个对象进入单调栈时，会从栈顶开始依次淘汰单调栈里对后续求解答案没有帮助的对象
（3）每个对象从栈顶弹出的时结算当前对象参与的答案，随后这个对象不再参与后续求解答案的过程
（4）其实是先有对题目的分析！进而发现单调性，然后利用单调栈的特征去实现
⚠️ 注意
单调栈可以和很多技巧交叉使用！比如：动态规划 + 单调栈优化，会在【扩展】课程里讲述
最大宽度坡
题目链接
https://leetcode.cn/problems/maximum-width-ramp/
思路分析
单调栈维护最大宽度坡左侧的可能性，找当前元素右侧比自己大的，栈中元素小压大
举例：[ 10，8，3，4 ... 5 ]，如果发现单调递增的趋势（3，4），3 作为左侧产生的坡度当然比 4 作为左侧的坡度大，即更左的位置，单调栈只需要关注单调递减的趋势，哪些元素可能作为坡度的左侧
入栈时从左到右，遍历时从右往左，这样才可以使得坡度尽可能的大，逐个弹出栈顶元素，匹配看是否满足条件
题中要求了 A [ i ] <= A [ j ] ，无需考虑相等时如何处理
代码实现
java
class Solution {
public int maxWidthRamp(int[] nums) {
int MAXN = 50001;
int[] stack = new int[MAXN];
// r = 1 相当于 0 位置进站了，栈大小为 1
int r = 1;
for (int i = 1; i < nums.length; i++) {
// 栈中维持单调递减的趋势，小压大
if (nums[stack[r - 1]] > nums[i]) {
stack[r++] = i;
}
}
// 从后往前遍历，逐个匹配
int ans = 0;
for (int j = nums.length - 1; j >= 0; j--) {
// 如果不满足坡度要求，跳过，也不弹出元素
while (r > 0 && nums[stack[r - 1]] <= nums[j]) {
ans = Math.max(ans, j - stack[--r]);
}
}
return ans;
}
}去除重复字母
题目链接
https://leetcode.cn/problems/remove-duplicate-letters/
思路分析
先记录每个字符的词频，由于都是字母，可以使用 ASCLL 码，目的是知道后面还有没有对应的字符，如果发现还有，那就将该字符从栈中弹出，让更小字典序的字符进栈，因为弹出的字符后面还有机会进入，所以可以弹出
因为要求字典序最小，即维持从小到大的单调性，可以使用大压小的单调栈，如果后面没有字符了，那只能接收破坏大压小的结果
代码实现
java
class Solution {
// 原来是 String s，这里改成 str
public String removeDuplicateLetters(String str) {
int MAXN = 26;
// 每种字符词频
int[] cnts = new int[MAXN];
// 每种字符目前有没有进栈
boolean[] enter = new boolean[MAXN];
// 单调栈
char[] stack = new char[MAXN];
Arrays.fill(cnts, 0);
Arrays.fill(enter, false);
int r = 0;
// 统计词频
char[] s = str.toCharArray();
for (char cha : s) {
cnts[cha - 'a']++;
}
for (char cur : s) {
if (!enter[cur - 'a']) {
// 栈中元素大压小
while (r > 0 && stack[r - 1] > cur && cnts[stack[r - 1] - 'a'] > 0) {
enter[stack[r - 1] - 'a'] = false;
r--;
}
stack[r++] = cur;
enter[cur - 'a'] = true;
}
// 字符在栈中，减少词频
cnts[cur - 'a']--;
}
return String.valueOf(stack, 0, r);
}
}⚠️ 大鱼吃小鱼问题
题目链接
bilibili 笔试真题
牛客：https://www.nowcoder.com/practice/77199defc4b74b24b8ebf6244e1793de
力扣：https://leetcode.cn/problems/steps-to-make-array-non-decreasing/
力扣题：使数组按非递减顺序排列，本质一样，换了一种问法
思路分析
左边吃右边，从右往左遍历，栈中元素维持小压大的结构
栈中元素结构：[ 值，轮数 ]
轮数：表示当前的鱼可能被其他鱼吃掉，其他鱼吃掉当前鱼之后接替当前鱼去吃其他鱼所需要的轮数
接替：可以理解为吃掉当前鱼之后，当前鱼去吃其他鱼还需要的轮数，干脆就替当前鱼吃了，即最后的轮数为 Math.max（吃掉当前鱼需要的轮数，轮数）
吃掉当前鱼需要的轮数 = 本身存储的轮数 + 1
⚠️ 注意：每条鱼吃比自己小的鱼的时候是同时发生的
牛客代码实现
java
import java.io.*;
public class Main {
public static int MAXN = 100001;
public static int[] arr = new int[MAXN];
public static int n;
public static int[][] stack = new int[MAXN][2];
public static int r;
public static void main(String[] args) throws IOException {
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; i >= 0; i--) {
// 初始轮数
int curTurns = 0;
// 从后往前遍历，栈中元素小压大
while (r > 0 && stack[r - 1][0] < arr[i]) {
curTurns = Math.max(curTurns + 1, stack[--r][1]);
}
// 相等直接进栈
stack[r][0] = arr[i];
stack[r++][1] = curTurns;
// 更新轮数
ans = Math.max(ans, curTurns);
}
return ans;
}
}力扣代码实现
java
class Solution {
public int totalSteps(int[] arr) {
int MAXM = 100001;
int[][] stack = new int[MAXM][2];
int r = 0;
int ans = 0;
for (int i = arr.length - 1; i >= 0; i--) {
// 初始轮数
int curTurns = 0;
// 从后往前遍历，栈中元素小压大
while (r > 0 && stack[r - 1][0] < arr[i]) {
curTurns = Math.max(curTurns + 1, stack[--r][1]);
}
// 相等直接进栈
stack[r][0] = arr[i];
stack[r++][1] = curTurns;
// 更新轮数
ans = Math.max(ans, curTurns);
}
return ans;
}
}统计全 1 子矩形
题目链接
https://leetcode.cn/problems/count-submatrices-with-all-ones/
思路分析
本题跟单调栈上中的最大矩形类似，使用压缩数组技巧，本题转为求矩形的个数，而不是求面积
要求每个元素左侧和右侧比当前元素小且最近的，分别记为 left，right，栈中元素的结构为大压小，要求以每一行为底，当前 i 位置的矩形个数转为求 [ n + 1，i ] 这些高度下的矩形有多少个，n 取 left 和 right 的最大值，矩形的宽 len = i - left - 1，即中间部分
取最大的原因：left 和 right 中较大的那个 + 1 到 i 范围这些高度的矩形一定包括了高度较矮情况下 + 1 的矩形
一个高度下的矩形个数为：ans = len * （len + 1） / 2
总的矩形个数 = ans * 高度范围的差值，以每一行为底加工柱状图，将所有答案累加起来即可
代码实现
java
class Solution {
public int numSubmat(int[][] mat) {
int MAXM = 151;
int[] height = new int[MAXM];
int[] stack = new int[MAXM];
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++) {
height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;
}
ans += countFromBottom(m, height, stack);
}
return ans;
}
// 比如
// 1
// 1
// 1 1
// 1 1 1
// 1 1 1
// 1 1 1
//
// 3 .... 6 .... 8
// left cur i
// 如上图，假设6位置从栈中弹出，6位置的高度为6(上面6个1)
// 6位置的左边、离6位置最近、且小于高度6的是3位置(left)，3位置的高度是3
// 6位置的右边、离6位置最近、且小于高度6的是8位置(i)，8位置的高度是4
// 此时我们求什么？
// 1) 求在4~7范围上必须以高度6作为高的矩形有几个？
// 2) 求在4~7范围上必须以高度5作为高的矩形有几个？
// 也就是说，<=4的高度一律不求，>6的高度一律不求！
// 其他位置也会从栈里弹出，等其他位置弹出的时候去求！
// 那么在4~7范围上必须以高度6作为高的矩形有几个？如下：
// 4..4 4..5 4..6 4..7
// 5..5 5..6 5..7
// 6..6 6..7
// 7..7
// 10个！什么公式？
// 4...7范围的长度为4，那么数量就是 : 4*5/2
// 同理在4~7范围上，必须以高度5作为高的矩形也是这么多
// 所以cur从栈里弹出时产生的数量 :
// (cur位置的高度-Max{left位置的高度,i位置的高度}) * ((i-left-1)*(i-left)/2)
// 柱状图中统计矩形
public int countFromBottom(int m, int[] height, int[] stack) {
int r = 0;
int ans = 0;
for (int i = 0; i < m; i++) {
// 找左右比自己小且最近的，栈中元素大压小
while (r > 0 && height[stack[r - 1]] >= height[i]) {
int cur = stack[--r];
// 相等直接弹出，后续能算对，不用处理
if (height[cur] > height[i]) {
// 只有height[cur] > height[i]才结算
// 如果是因为height[cur]==height[i]导致cur位置从栈中弹出
// 那么不结算！等i位置弹出的时候再说！
// 上一节课讲了很多这种相等时候的处理，比如"柱状图中最大的矩形"问题
int left = r == 0 ? -1 : stack[r - 1];
int len = i - left - 1;
int bottom = Math.max(left == -1 ? 0 : height[left], height[i]);
ans += (height[cur] - bottom) * len * (len + 1) / 2;
}
}
stack[r++] = i;
}
// 清算阶段
while (r > 0) {
int cur = stack[--r];
int left = r == 0 ? -1 : stack[r - 1];
int len = m - left - 1;
int down = left == -1 ? 0 : height[left];
ans += (height[cur] - down) * len * (len + 1) / 2;
}
return ans;
}
}