算法通关--单调栈
单调栈
单调栈是在栈的先进后出的规则基础上，要求从栈底到栈顶的元素满足单调的关系。如果是大压小，那么从栈顶观察是递减栈，如果是小压大，那么从栈顶观察使递减栈
经典用法：
判断一个数组每个位置都求：
1.当前位置的 左侧比当前位置的数字小（大），且距离最近的位置在哪
2.当前位置的 右侧比当前位置的数字小（大），且距离最近的位置在哪
如果按照暴力求解，那么时间复杂度来到了O(N^2)，但是对于单调栈来说，时间复杂度为O(N)
1.数组无重复值的情况
下面有数组[2,5,6,1,4,7,5],找出数组中比当前位置数字小的左右的位置。我们建立一个栈，栈内的元素服从数值大压小的规则，并且栈中放的是下标，因为可以通过下标来找到数组中对应位置元素的值。注：0-->2表示的是下标0位置的元素2
0-->2进栈，1-->5进栈，2-->6进栈，1-->4准备进栈，发现栈顶元素6比自己大，那么元素6出栈，元素6压的是元素5，因此元素6左边离自己最近且小于自己的位置是1-->5，3-->1使自己出去，那么右边离自己最近且小于自己的位置是3-->1，如图：
但是2-->6出栈后，3-->1可以进栈吗，不能！！！因为1-->5比1大，0-->2比1大，当它们两个出栈后，3-->1就可以进栈了，此时可以得到：
| 左 | 右 | |
| 2-->6 | 1-->5 | 3-->1 |
| 1-->5 | 0-->2 | 3-->1 |
| 0-->2 | -1 | 3-->1 |
之后4-->4进栈，5-->7进栈，6-->5进栈前弹出5-->7,最终得到栈中的元素以及列表如下：左边为-1，表示为栈底元素，在数组中的表现是左边没有比自己元素小的数字
| 左 | 右 | |
| 2-->6 | 1-->5 | 3-->1 |
| 1-->5 | 0-->2 | 3-->1 |
| 0-->2 | -1 | 3-->1 |
| 5-->7 | 4-->4 | 6-->5 |
数组中没有可以压栈的数字了，进入清算阶段，清算阶段栈中的右边均为-1，（没有元素使自己弹出），右边为自己压的元素。那么最终形成的列表为：
| 当前位置 | 左 | 右 |
| 2-->6 | 1-->5 | 3-->1 |
| 1-->5 | 0-->2 | 3-->1 |
| 0-->2 | -1 | 3-->1 |
| 5-->7 | 4-->4 | 6-->5 |
| 6-->5 | 4-->4 | -1 |
| 4-->4 | 3-->1 | -1 |
| 3-->1 | -1 | -1 |
2.数组有重复值的情况
当遇到有重复值的情况，对于重复的数值先进栈的元素进行弹栈，后进栈的元素进行压栈，对于进行弹栈的元素记录左右位置的元素，即使右边的元素可能不对，但是在最后的阶段进行修正。
例如：数组[2,4,3,5,2,6],求每个位置的数字离自己最近的最小值元素，按照上面的操作，最终得到以下列表
| 当前位置 | 左 | 右 |
| 1-->4 | 0-->2 | 2-->3 |
| 3-->5 | 2-->3 | 4-->2 |
| 2-->3 | 0-->2 | 4-->2 |
| 0-->2 | -1 | 4-->2 |
| 5-->6 | 4-->2 | -1 |
| 4-->2 | -1 | -1 |
比较当前位置的元素和表格中右边位置的元素，如果比自己小，那么没有问题，如果和自己相等，那么取表格右边位置的下标的右边的值。例如：0-->2的右边是4-->2，这个有问题，那么0-->2右边是4位置右边填的数值-1。由于栈中的元素是大压小，因此左侧求出的元素没有问题
例题1:
单调栈结构(进阶)_牛客题霸_牛客网
我们利用数组进行栈的实现，其中r表示栈中的剩余的元素，ans[][]表示答案的二维数组：代码如下：
#include <iostream>
using namespace std;
const int MAXN = 1000001;
int arr[MAXN];
int ans[MAXN][2];
int n, r;
// 数组模拟实现栈
void compute() {
int stack[MAXN];
r = 0; // 表示栈的状态
int cur; // 答案数组的指针
for (int i = 0; i < n; i++) {
// 构建一个大压小的单调栈，如果栈不为空，且不满足大压小，进行while循环(弹栈)
while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
cur = stack[--r];
// cur当前弹出的位置,左边是栈顶元素，右边是让自己弹出位置的元素
ans[cur][0] = r > 0 ? stack[r - 1] : -1;
ans[cur][1] = i;
}
// 要么栈为空 要么是 arr[i] > 栈顶元素，进栈
stack[r++] = i;
}
// 清算阶段 -- 栈里还有剩余
while (r > 0) {
cur = stack[--r];
ans[cur][0] = r > 0 ? stack[r - 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];
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
compute();
for (int i = 0; i < n; i++) {
cout << ans[i][0] << " " << ans[i][1] << endl;
}
return 0;
}
例题2：
https://leetcode.cn/problems/daily-temperatures/
对于temperatures=[73,74,75,71,69,72,76,73]来说，如果建立大压小的栈，那么求出每一个位置的值使小于当前位置的天数，与题意要求的不符，因此建立小压大的栈，使当前位置弹出的位置减去当前位置即为答案，在清算阶段，直接为0。例如，1位置的74使0位置的73弹出，那么答案数组中的ans[0]就是1.代码如下
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> s;
// 构建小压大的栈，栈中记录的是下标！！！
for (int i = 0; i < n; i++) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) { // 不为空且不能大压小
int top = s.top();
ans[top] = i - top; // 记录应该放那个数字，哪个位置的比他大
s.pop(); // 弹出
}
// 为空or小压大
s.push(i);
}
// 数组初始化时每个位置为0，因此直接返回
return ans;
}例题3：
907. 子数组的最小值之和 - 力扣（LeetCode）
如果是分别求出每一个子数组，在从子数组中挑选最小值相加的话，太慢了，利用单调栈怎么解？
既然是子数组，那就是一个区间，求一个区间的最小值，一个区间往外扩，未扩充之前的最小值一定大于等于扩充之后的最小值。那么在一个区间内的最小值，它的区间左边界的左边的值一定小于等于当前区间的最小值，它的区间右边界的右边的值一定小于等于当前区间的最小值，例如：
2|9 7 6 8|1，对于| |区间的最小值6来说，2和1均比6小。那么这个和单调栈有什么关系？
我们继续看：只要过在这个数组区间内，过6的子区间，最小值一定是6 ，即[9,7,6],[9,7,6,8],[7,6],[7,6,8],[6],[6,8]这些子区间都是以6为最小值，那么这些子区间的最小值为6*6=36；这不就求出和了吗，6这个区间长度怎么快速得到，就是单调栈，（当前位置的下标值-它的左边）*（它的右边当前位置的下标值），即（3-0）*（5-3） = 6；
const int MOD = 1000000007;
const int MAXN = 30001;
int stack[MAXN];
int r;
int sumSubarrayMins(vector<int>& arr) {
long long ans = 0;
r = 0;
for (int i = 0; i < arr.size(); i++) {
while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
int cur = stack[--r];
int left = r == 0 ? -1 : stack[r - 1];
ans = (ans + (long 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 long)(cur - left) * (arr.size() - cur) * arr[cur]) % MOD;
}
return (int)ans;
}例题4：
84. 柱状图中最大的矩形 - 力扣（LeetCode）
这个题怎么看，找以每个位置为高度，求可以拼成的最大矩形，左边对于比自己高的，可以扩充，比自己低的不可以扩充，那么这个就是求得每一个位置左比自己小的数，例如[2,1,5,6,2,3]，对于0位置的2来说，左边没有，扩大不了，右边比自己小，扩不了，那么面积就是2；对于1位置的1来说，左边扩1个，右边扩4个，面积是6*1；对于2位置的5来说，左边不能扩，右边扩1个，面积为2*5=10；对于3位置的6来说，左边不能扩，右边不能扩，面积1*6，对于4位置的2来说，左边扩2个，右边扩1个，面积为4*2=8，对于5位置的3来说，左边不能扩，右边不能扩，面积为3；最终的整体为10.还是根据单调栈的模板，求得左边和右边比自己小值的位置
注意区间的长度，当地位置为i，由于是减小就往左扩，当while循环进不去的时候，左边的下标不在“可扩增区间内”，例如[2,1,5,6,2,3]，当i在5位置的2时，i==4,对数值6得出left==2，因为此时3位置的6已经弹栈，那么获取的top就是2位置，i-left-1==1,符合条件。注意：弹出谁是才能算出该位置的矩形面积，那么最终代码是：
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
stack<int> s;
n = heights.size();
for (int i = 0; i < heights.size(); i++) {
while (!s.empty() && heights[i] < heights[s.top()]) {
int cur = s.top();
s.pop();
int left = s.empty() ? -1 : s.top();
ans = max(ans, (i - left - 1) * heights[cur]); // 算面积！！！一定注意！！！
}
s.push(i);
}
while (!s.empty()) {
int cur = s.top();
s.pop();
int left = s.empty() ? -1 : s.top();
ans = max(ans, (n - left - 1) * heights[cur]);
}
return ans;
}例题5：
962. 最大宽度坡 - 力扣（LeetCode）
题目要求的满足条件i<j并且arr[i]<arr[j]，求j-i的最大值，首先构建一个严格小压大的栈（不进行弹栈，只压栈），严格小压大就是如果遇到和栈顶相同的数值，不压栈，这样子做的好处是如果后面的数值比栈顶大，那么下标减去先压栈的下标一定大于下标减去后压栈的下标，（一句话，先压栈求的结果更大，更符合题意）。
构建完后，从数组右边开始，比栈顶元素大，计算距离，弹出栈顶元素，（这是因为如果不弹出，下一个比栈顶大的算的距离一定比当前距离小，例如x-y，x一直减小对于从右向左走，y不变对应栈顶不弹出。。。）
int maxWidthRamp(vector<int>& nums) {
int stack[50001] = { 0 };
r = 1; // 令r=1相当于0位置进栈了
int n = nums.size();
// 构建小压大的单调栈 -- 存储的是数组的下标
for (int i = 1; i < n; i++) {
if (nums[stack[r - 1]] > nums[i]) {
stack[r++] = i;
}
}
int ans = 0;
// 从右往左找答案,比栈顶元素大，计算答案，栈顶弹出
for (int j = n - 1; j >= 0; j--) {
while (r > 0 && nums[stack[r - 1]] <= nums[j]) {
ans = max(ans, j - stack[--r]);
}
}
return ans;
}