单调栈

笔者在做leetcode的题(下一个出现的最大数字)时，接触到了单调栈这一种数据结构，经过研究之后，发现单调栈在解决某些问题时出奇的好用，下面是对单调栈的性质和一些典型题目。

什么是单调栈？

从名字上就听的出来，单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈

单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大

模拟单调栈的数据push和pop

模拟实现一个递增单调栈：

现在有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。

10入栈时，栈为空，直接入栈，栈内元素为10。
3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。
7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。
4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。
12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。

单调栈的伪代码

stack<int> st;
//此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
for (遍历这个数组)
{if (栈空 || 栈顶元素大于等于当前比较元素){入栈;}else{while (栈不为空 && 栈顶元素小于当前元素){栈顶元素出栈;更新结果;}当前数据入栈;}
}

单调栈的应用

单调栈的应用我们直接拿一些具体的题来对照应用：

1.视野总和

描叙：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2
解释：个子为4的可以看到个子为3的发型，个子为7可以看到个子为1的身高，所以1+1=2
思路：观察题之后，我们发现实际上题目转化为找当前数字向右查找的第一个大于他的数字之间有多少个数字，然后将每个结果累计就是答案，但是这里时间复杂度为O(N^2)，所以我们使用单调栈来解决这个问题。

1.设置一个单调递增的栈（栈内0~n为单调递减）
2.当遇到大于栈顶的元素，开始更新之前不高于当前人所能看到的值
在这里插入图片描述

int FieldSum(vector<int>& v)
{v.push_back(INT_MAX);/这里可以理解为需要一个无限高的人挡住栈中的人，不然栈中元素最后无法完全出栈stack<int> st;int sum = 0;for (int i = 0; i < (int)v.size(); i++){if (st.empty() || v[st.top()] > v[i])//小于栈顶元素入栈{st.push(i);}else{while (!st.empty() && v[st.top()] <= v[i]){int top = st.top();//取出栈顶元素st.pop();sum += (i - top - 1);//这里需要多减一个1}st.push(i);}}return sum;
}

2.柱状图中的最大矩形

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
在这里插入图片描述

思路：当前的数字可以向两边拓展，遇到比自己大的就接着拓展，小的就停止，然后用自己的高度乘以拓展的宽度，每次都跟新最大面积，时间复杂度同样为O(N^2)，所以我们接着借助单调栈

上面使用了单调递增栈，这里我们通过这道例题来使用一下单调递减栈

1.设置一个单调递减的栈（栈内0~n为单调递增）
2.当遇到小于栈顶元素的值，我们开始更新数据，因为有可能最大面积就会出现在栈中的序列里
3.牢记栈中数据永远是有序的，这个问题比较复杂，所以读者不妨对照着代码来理解问题

int largestRectangleArea(vector<int>& heights) {heights.push_back(-1);/同理，我们希望栈中所有数据出栈，所以给数组最后添加一个负数stack<int> st;int ret = 0, top;for (int i = 0; i < heights.size(); i++){if (st.empty() || heights[st.top()] <= heights[i]){st.push(i);}else{while (!st.empty() && heights[st.top()] > heights[i]){top = st.top();st.pop();//i-top指的是当前矩形的宽度，heights[top]就是当前的高度//再次强调栈中现在为单调递增int tmp = (i - top)*heights[top];if (tmp > ret)ret = tmp;}st.push(top);heights[top] = heights[i];}}return ret;
}

很多读者不太懂下图这两句代码：
在这里插入图片描述
假设遇到了小于栈顶的数据，我们需要判断下图中哪个矩形更大，并且跟新数据，这里应该都可以理解，我们将图中三个数据标记为0，1，2.接着往下看

因为需要保持栈中递增的属性，所以栈中只有i一个数据：
在这里插入图片描述
但是对于当前元素来说下标为0，1的元素都比他大，所以那么就意味着它可以向左延申扩大矩形：像下图那样

但是我们为了保持栈中的递增属性，并且可以让i可以向左拓展，我们索性修改了i的下标，将他修改为最左边的top下标，所以当我们下次需要以他为基准获取矩形面积时就像这样
在这里插入图片描述
所以假设我们数组中的4个数据（实际是5个，最后一个数字用来出栈所有数据）全部访问完时：如下面的方式计算矩形

ps：如果有的同学还是不清楚，可以用自己的编译器调试一下。

3.求最大区间

描述：给出一组数字，求一区间，使得区间元素和乘以区间最小值最大，结果要求给出这个最大值和区间的左右端点
输入：3 1 6 4 5 2
输出：60
3 5
解释：将3到5（6+4+5）这段区间相加，将和与区间内最小元素相乘获得最大数字60
思路：使用暴力解法求出所有区间，再求出区间的最小值相乘跟新数据，并不是一种很好的算法，所以经过上面俩题的磨炼，此时我们应该使用一个单调递减栈

1.设置一个单调递减的栈（栈内0~n为单调递增）
2.当遇到小于栈顶元素的值，我们开始更新数据，因为当前遇到的值一定是当前序列最小的

int GetMaxSequence(vector<int>& v)
{stack<int> st;vector<int> vs(v.size()+1);vs[0] = 0;for (int i = 1; i < vs.size(); i++){vs[i] = vs[i - 1] + v[i-1];}v.push_back(-1);int top, start, end, ret = 0;for (int i = 0; i < v.size(); i++){if (st.empty() || v[st.top()] <= v[i]){st.push(i);}else{while (!st.empty() && v[st.top()] > v[i]){top = st.top();st.pop();int tmp = vs[i] - vs[top];tmp = tmp * v[top];if (tmp > ret){ret = tmp;start = top+1;end = i;}}st.push(top);v[top] = v[i];//与第二题相同的道理，将当前数据的更改最左的top下标，防止出现比当前数据更小的数据//这句在这道题里真的超级难理解，但是只要你有耐心相信你可以理解的}}return ret
}