单调栈-上
基本介绍
应用场景
每个位置都求小，栈底到栈顶从小到大，大压小
（1）当前位置的左侧比当前位置的数字小，且距离最近的位置在哪
（2）当前位置的右侧比当前位置的数字小，且距离最近的位置在哪
每个位置都求大，栈底到栈顶从大到小，小压大
（1）当前位置的左侧比当前位置的数字大，且距离最近的位置在哪
（2）当前位置的右侧比当前位置的数字大，且距离最近的位置在哪
用单调栈的方式可以做到：求解过程中，单调栈所有调整的总代价为 O（n），单次操作的均摊代价为 O（1）
⚠️ 注意
单调栈可以和很多技巧交叉使用！比如：动态规划 + 单调栈优化，会在【扩展】课程里讲述
解题思路
⚠️ 注意：栈中存储的是元素的下标索引，以下的思路描述求小的情况，即从栈底到栈顶存储下标对应的元素大小依次从小到大排序，使用数组实现栈，优化常数时间
（1）无重复数值数组
如果即将压入的元素比栈顶元素大，直接压入，栈中维持的单调性是从栈底到栈顶是从小到大的
如果即将压入的元素比栈顶元素小，弹出栈顶元素，记为 n，则 n 左边比 n 小且最近的为新的栈顶元素，n 右边比 n 小且最近的为让 n 弹出的元素，如果不存在，记为 -1
遍历完所有元素，如果栈中还有元素，依次弹出，左边的答案符合上述规则，右边的答案全为 -1
（2）⭐有重复数值数组
首先以无重复数组为基础，先记录答案，后续修正右侧的答案，如果是 -1 无需修正
修正阶段：从右往左遍历，如果发现当前位置的值和当前位置右侧的答案相等，则修正当前位置右侧的答案为当前位置右侧答案值的右侧答案
💡 难点
当前遍历元素和栈顶元素相等时，此时栈顶元素右侧的答案按理说是当前遍历元素，但是可能是错的，而后续等待遍历的数才是当前栈顶元素右侧的正确答案，此时该如何结算答案？
根据题目具体分析，一般无需处理，因为后续的数可以使得最终答案正确
模板题
题目链接
https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb
代码实现
java
import java.io.*;
public class Main {
public static int MAXN = 1000001;
public static int[] arr = new int[MAXN];
public static int[] stack = new int[MAXN];
// ans[i] --> [左边的答案][右边的答案]
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++) {
out.println(ans[i][0] + " " + ans[i][1]);
}
}
out.flush();
out.close();
br.close();
}
// 使用数组实现栈，优化常数时间
// 栈中存储的是元素的下标
public static void compute() {
// 使用静态空间，先清理脏数据
// r 表示栈中元素的个数
r = 0;
int cur;
// 遍历阶段
for (int i = 0; i < n; i++) {
// 只要遍历元素比当前栈顶元素小
// 弹出栈顶元素，记录答案
// 直到自己可以压入栈中才停止
while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
// 栈顶元素对应的下标
cur = stack[--r];
// 记答案
// 左侧答案：原栈中 cur 的下一个元素，即新的栈顶元素
// 右侧答案：让 cur 弹出的元素
ans[cur][0] = r > 0 ? stack[r - 1] : -1;
ans[cur][1] = i;
}
// 将当前遍历的元素入栈
stack[r++] = i;
}
// 清算阶段：元素遍历完，栈中还有元素
while (r > 0) {
cur = stack[--r];
ans[cur][0] = r > 0 ? stack[r - 1] : -1;
// 是自己弹出的，并不是某个元素让其弹出的
// 所以右侧答案均为 -1
ans[cur][1] = -1;
}
// 修正阶段：数组中出现了重复元素
// 左侧答案一定正确，从右往左遍历修正右侧答案
// n-1 位置的右侧答案一定为 -1，不需要修正
for (int i = n - 2; i >= 0; i--) {
if (ans[i][1] != -1 && arr[ans[i][1]] == arr[i]) {
ans[i][1] = ans[ans[i][1]][1];
}
}
}
}每日温度
题目链接
https://leetcode.cn/problems/daily-temperatures/
思路分析
本题就是找比当前元素大且最近的，计算差值，栈的结构是栈底到栈顶从大到小，小压大
如果右侧答案不存在，记为 0，因为不需要维护左侧，所以清算阶段可以省去，数组的初始值天然为 0，无需手动处理
代码实现
java
class Solution {
// 原来是 int[] temperatures，这里改成 nums
public int[] dailyTemperatures(int[] nums) {
// 数组实现栈，优化常数时间
int MAXN = 100001;
int[] stack = new int[MAXN];
int n = nums.length;
int[] ans = new int[n];
int r = 0;
for (int i = 0; i < n; i++) {
// 找右侧大且最近的，栈中元素小压大，严格小于，弹出的逻辑
// 不取等，模板中取等是因为后续有修正逻辑可以修正对
while (r > 0 && nums[stack[r - 1]] < nums[i]) {
int cur = stack[--r];
ans[cur] = i - cur;
}
// 相等也入栈，后续一定能将最终答案算对
stack[r++] = i;
}
return ans;
}
}子数组的最小值之和
题目链接
https://leetcode.cn/problems/sum-of-subarray-minimums/
思路分析
题目要求对答案取模，使用同余定理
对于 i 位置的元素，找到左边比 i 小且最近的，记为 left 位置，找到右边比 i 小且最近的，记为 right 位置，那就说明 [ left + 1，right + 1 ] 这个范围内，i 位置的数一定是最小的
利用上面这个特性就可以找到所有包含 i 位置这个最小值的子数组，所有子数组左侧位置的可能性为 i - left，右侧位置的可能性为数组长度 n - i，则子数组的数量为 （i - left） * （n - i）
举例：i 遍历到 3 位置，左侧比 i 小且最近的元素再 1 位置，右侧比 i 小且最近的元素再 7 位置，则组成子数组可能的位置为 2-3，2-4，2-5，2-6，3-3，3-4，3-5，3-6，那子数组左侧的可能性为 i - left = 3 - 1 = 2，右侧的可能性为 n - i = 7 - 3 = 4，所有子数组的个数为 2 * 4 = 8
代码实现
java
class Solution {
public int sumSubarrayMins(int[] arr) {
int MOD = 1000000007;
int MAXN = 30001;
int[] stack = new int[MAXN];
int r = 0;
long ans = 0;
for (int i = 0; i < arr.length; i++) {
// 找右侧比 i 位置小且最近的，栈中元素大压小
// 相等正常算，后面一定可以修正对
while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
int cur = stack[--r];
int left = r == 0 ? -1 : stack[r - 1];
// 子数组开头位置的可能性：cur - left
// 子数组结尾位置的可能性：arr.length - cur
// 利用加法同余定理计算
ans = (ans + (long) (cur - left) * (i - cur) * arr[cur]) % MOD;
}
stack[r++] = i;
}
// 清算阶段
while (r > 0) {
int cur = stack[--r];
int left = r == 0 ? -1 : stack[r - 1];
ans = (ans + (long) (cur - left) * (arr.length - cur) * arr[cur]) % MOD;
}
return (int) ans;
}
}柱状图中的最大矩形
题目链接
https://leetcode.cn/problems/largest-rectangle-in-histogram
思路分析
遍历每一个柱子，找当前柱子左边比柱子小且最近的柱子，记为 left，找当前柱子右边比柱子小且最近的柱子，记为 right，目的是能以当前柱子为基准往两边扩展，使得面积尽可能的大，如果不存在则记为 -1
面积为中间的部分：height[cur] * （right - left - 1）
代码实现
java
class Solution {
public int largestRectangleArea(int[] heights) {
int MAXN = 100001;
int[] stack = new int[MAXN];
int r = 0;
int ans = 0;
for (int i = 0; i < heights.length; i++) {
// 相等也弹出，后面能算对
while (r > 0 && heights[stack[r - 1]] >= heights[i]) {
int cur = stack[--r];
int left = r == 0 ? -1 : stack[r - 1];
ans = Math.max(ans, heights[cur] * (i - left - 1));
}
stack[r++] = i;
}
// 清算阶段
while (r > 0) {
int cur = stack[--r];
int left = r == 0 ? -1 : stack[r - 1];
ans = Math.max(ans, heights[cur] * (heights.length - left - 1));
}
return ans;
}
}最大矩形
题目链接
https://leetcode.cn/problems/maximal-rectangle/
思路分析
压缩数组技巧，以每行作为底，加工柱状图，问题转为柱状图中的最大矩形问题，每行求一个答案，不断更新最大值，时间复杂度：O（n * m）
代码实现
java
class Solution {
// 原来是 char[][] matrix，这里改成 grid
public int maximalRectangle(char[][] grid) {
int MAXN = 201;
int[] height = new int[MAXN];
int[] stack = new int[MAXN];
int n = grid.length;
int m = grid[0].length;
Arrays.fill(height, 0, m, 0);
int ans = 0;
for (int i = 0; i < n; i++) {
// 来到第 i 行，以改行为底，加工柱状图
for (int j = 0; j < m; j++) {
height[j] = grid[i][j] == '0' ? 0 : height[j] + 1;
}
ans = Math.max(largestRectangleArea(m, height, stack), ans);
}
return ans;
}
// 柱状图中的最大矩形面积，找左右比 i 小且位置最近的
public int largestRectangleArea(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];
int left = r == 0 ? -1 : stack[r - 1];
ans = Math.max(ans, height[cur] * (i - left - 1));
}
stack[r++] = i;
}
// 清算阶段
while (r > 0) {
int cur = stack[--r];
int left = r == 0 ? -1 : stack[r - 1];
ans = Math.max(ans, height[cur] * (m - left - 1));
}
return ans;
}
}