$jxwd系列专题——LeetCode精讲，每次都讲点和官方题解不一样的东西$
（本文为独家原创 By 阿祥）
看完本节内容，你将收获：一种思想，四个习题（其中三个为LeetCode上Hard难度）
同时，我们将会在文末放上七道LeetCode上有关单调栈的习题，供大家思考提升（并会附上我们推荐的题解）。
我们将采用图片、视频、文字描述的方式来帮助大家理解。
我们的定位是：让没有接触过这块知识的同学也能够轻松看懂。（如需转载，请注明原文出处和作者呦）
单调栈的问题，一般情况下在柱形图当中用到的比较多，它是一种非常巧妙的方法，在很多场合下能够帮助同学们“化险为夷”、“绝处逢生”哈哈。
我们单调栈，主要来讲解四个题：
1、单调栈直接应用题：（节选自《程序员代码面试指南 · IT名企算法与数据结构题目最优解》（左程云 著））
给定一个不含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置，返回所有位置相应的信息。
//样例：输入
int arr[] = {3, 4, 1, 5, 6, 2, 7};
输出返回以下二维数组作为结果：
{ {-1，2}, {0, 2}, {-1, -1}, {2, 5}, {3, 5}, {2, -1}, {5, -1} }
2、84. 柱状图中最大的矩形 - 力扣（LeetCode）
（难度Hard）
3、85. 最大矩形 - 力扣（LeetCode）
（下题二维数组图）
4、32. 最长有效括号 - 力扣（LeetCode）
OK，感兴趣的小伙伴可以自己先构思构思，看看有没有思路，如果有，看看能不能优化（如果没有也没有关系的哈哈哈哈哈）。
在此之前，我们会详细地介绍单调栈有关的知识。如果你对单调栈已经完全掌握了，那么就可以直接从第二题开始肝啦~~~~~~
穿插：单调栈基础知识介绍
我们首先来介绍单调栈的基础知识，然后再来利用单调栈的有关思想，来尝试解决这些题目。
单调栈，顾名思义是单调的栈结构；即在一个栈结构中，其栈中的元素从栈底往栈顶看（或者从栈顶往栈底看）是单调的。即要么是单调增，要么是单调减。
就类似于这样：（如下图所示）
如上图所示，在这样一个栈结构当中，自栈底->栈顶来看，元素为10，9，8，7；像这样的结构，即叫做单调栈结构。
那么，我们怎么样来去维护这样一个单调栈结构呢？
我们先写出一个伪代码，然后举一个例子，来帮助大家理解。
假设现在已经有了一个单调栈，自 栈底 到 栈顶 递减；此时有一个元素即将入栈。
分为两种情况：（记为步骤A）
1、它比栈顶的元素要小。
2、它大于等于栈顶的情况。（我们假设我们要维护的单调栈是严格单调的，不允许存在相邻两个元素大小相等的情况）
对于第一种情况，****我们直接将该结点压入栈顶中即可，因为我们在这个时候会发现，在此种情况下，将该元素压入了栈中，得到的栈结构依然满足原来的严格单调结构。
对于第二种情况，就稍微复杂一点点。第二种情况是要来的元素是要比栈顶的元素大的，因此，我们的做法是：
1、将栈顶元素弹出。
2、然后如果栈不为空，继续比较栈顶元素和该元素。重复步骤A。
直到没有元素入栈为止。
那么单调栈的伪代码，我们可以这样来去理解：
stack<int> stk;//我们假设想要维护一个从栈底到栈顶单调递减的单调栈
for(){//循环遍历要入栈的每一个元素
while(){//如果栈为空或者即将入栈的元素大于栈顶元素
//栈顶元素出栈
}
//该元素入栈
}
还是以上图的栈结构为例，现在我们来举一个例子：
//假设我们有一个数组，数组中的元素要依次入栈，并维护一个单调栈
vector<int> v = {10, 9, 8, 7, 6, 5, 7, 3, 4};
stack<int> stk;
for(int i = 0;i < v.size(); i++) { //让数组中的元素依次入栈
while(!stk.empty() && v[i] >= stk.pop()){ //如果栈不为空，并且栈顶元素比该元素要小
stk.pop(); //那么就pop()栈顶元素，直到栈顶元素比该元素大为止
}
stk.push(v[i]);//将该元素压入栈中，当然也可以存储下标
}
这样以后，我们就能够的得到这样一个栈，
如下图所示：
下图为每一个元素出栈、入栈的详细过程。
在这样一个过程当中，我们维护的是一个从栈底到栈顶元素单调递减的栈。
为了便于大家更直观地理解，我们还做了视频来帮助大家模拟元素出入单调栈的过程。（由于一些原因，动画视频我们做的是简易版本）戳下面链接可以观看：
单调栈图示-CSDN直播
单调栈图示
至此，我们将单调栈的结构已经完全介绍清楚。
那么在做具体的问题之前，来思考这样一个问题：
单调栈能用来干嘛呢？
所有的单调栈，不论题目怎么变化，本质上都用来做这样一件事情：
即所有的单调栈归根结底、从本质上来说，就是找到 某个数 的 左边或者右边第一个 比它大或者小的数。
这是极为凝练的概括。
比如刚刚的数组v:
vector<int> v = {10, 9, 8, 7, 6, 5, 7, 3, 4};
我们随便挑个数来研究，假设挑从左向右数第二个7（也就是数组下标为7所对应的元素）：
对于该元素而言，通过上述的单调栈（维护一个从栈底往栈顶看单调减的栈）就是找到了7左边第一个比自己大的数和右边第一个比自己小的数（关于这点读者可先自己思考下为什么，我们后文会再来详细介绍原因）
聪明的同学其实已经发现了，研究它的作用也就是我们的第一题答案。
没错，因为第一题就是为单调栈的引入而量身定做的，而后面几道题都是它的应用及其变式了。
OK，我们现在正式结合题目，为大家讲解单调栈的用武之地，同时，把LeetCode上的Hard题变成小菜鸡。
第一题题解
为了方便大家阅读，我们把题目复制到这个位置来：
题目：
给定一个不含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置，返回所有位置相应的信息。
//样例：输入
int arr[] = {3, 4, 1, 5, 6, 2, 7};
输出返回以下二维数组作为结果：
{ {-1，2}, {0, 2}, {-1, -1}, {2, 5}, {3, 5}, {2, -1}, {5, -1} }
注意，在样例中，-1表示不存在。
假设同学们还没有学习过单调栈，或者最先想到的应当是什么方法呢？没错，就是O(N^2)的暴力遍历。即在每个位置都向左和向右去遍历一下，直到碰到第一个比自己小的数时停止。
我们提一下这种方法，不做重点讲解了，也比较简单易懂。
参考代码（C++）
class Solution {
public:
vector<vector<int>> rightWay(vector<int> arr) {
int n = arr.size();
vector<vector<int>> res(n, vector<int>(2, -1));//创建一个二维数组并初始化（这也是我们最终将要返回的答案）
for (int i = 0; i < arr.size(); i++) {
int LeftIndex = -1;
int RightIndex = -1; //定义左边最小和右边最小，并初始化为-1
int cur = i - 1;
while (cur >= 0) {
if (arr[cur] < arr[i]) { //往左找比它小的数
LeftIndex = cur; //找到了以后就给LeftIndex
break; //然后跳出循环
}
cur--; //否则cur--，即继续往左找
}
cur = i + 1;
while (cur < arr.size()) { //同理往右找
if (arr[cur] < arr[i]) {
RightIndex = cur;
break;
}
cur++;
}
res[i][0] = LeftIndex; //一个数找完以后，将一个数的位置的LeftIndex和RightIndex赋到相应数组里去
res[i][1] = RightIndex;
}
return res;
}
};
注意到我们此时的算法的时间复杂度是O(N^2)，对于这样一个问题来说，复杂度还是比较高的。
我们有没有什么办法将其优化一下呢？
当然是有的，就用我们刚刚所介绍到的单调栈结构。
那具体怎么样来去实现呢？
我们还是老样子，给出详细的流程图、代码、代码注释、文字说明，并举例分析。（注：一切都是以能理解代码为核心，倘若能够直接理解代码，那也就不需要看其他的解释说明啦）
我们有两种思路都可以去实现它
->即我们可以维护一个从栈底到栈顶严格递增的栈；也可以去维护一个从栈底到栈顶严格递减的栈。
①维护一个从栈底到栈顶单调递增的单调栈。（推荐）
这样的话，我们能够实际上在栈中就已经找到了左侧的最近最小值了，而我们是从左往右去遍历，如果一个元素比栈顶元素要小，那么栈顶元素就要pop()，而在pop()的同时，我们就可以确定其右侧最近最小值就是该元素。（理由：既然栈顶元素pop()，那么该元素一定比栈顶元素小，又由于其是栈顶元素，所以其不可能存在介于二者之间的数。因此综上，该数就是栈顶元素右侧最近最小值）
最后将数组元素遍历完后，再将栈中元素清算。
图示：
（上图为每一个元素出栈、入栈的详细过程）
为什么推荐维护这样一个栈，而不是维护一个从栈底到栈顶单调减的单调栈呢？
其实用这两种栈来做都可以，只不过，对于本道题而言，维护从栈底到栈顶单调递增的单调栈有助于我们直接了当的找到最近最小值。（我们下面一种方法即是维护从栈底到栈顶严格递减的栈）
参考代码：（C++）
class Solution {
public:
vector<vector<int>> rightWay(vector<int> arr) {//int arr[] = {3, 4, 1, 5, 6, 2, 7};
int n = arr.size();
vector<vector<int>> res(n, vector<int>(2, -1));//创建一个二维数组并初始化（这也是我们最终将要返回的答案）
stack<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && arr[stk.top()] >= arr[i]) {//倘若考虑有值相等的情况，则加上等号；
//如果不考虑值相等的情况，则可以不用加
int popIndex = stk.top(); //取出栈顶元素
stk.pop();
int LeftIndex = stk.empty() ? -1 : stk.top();//判断此时是否为空，如果为空，则定义为-1
res[popIndex][0] = LeftIndex; //下标赋值
res[popIndex][1] = i;
}
stk.push(i); //将此时的下标压入栈中
}
while (!stk.empty()) {
int popIndex = stk.top(); //清算栈中剩余的元素
stk.pop();
int leftIndex = stk.empty() ? -1 : stk.top();
res[popIndex][0] = leftIndex;
res[popIndex][1] = -1;
}
return res;
}
};
②我们维护一个从栈底到栈顶严格递减的单调栈。（如下图）
如上图所示，从前往后顺序遍历一遍数组后，找出了每个数左侧比自己小的最近的下标；
然后用同样的方法，从后向前遍历数组（逆序遍历数组），得到每个数右侧比自己小的数的最近的下标。
由于这种方法比较麻烦，所以我们就不提供代码了，只提供思路，有兴趣的读者可自行编码。
不过相信各位通过这道题以及前面的描述已经大概了解到了单调栈是一个什么样的东西以及它拥有什么样的作用了。我们现在就来运用单调栈，尝试解决问题。
第二题题解
为了方便大家阅读，我们再将题目拿到这里来：
本题可谓是一道典型的单调栈问题。
当然，看到这道题，首先要说的是，我们还是要会暴力解法的。
暴力算法怎么写？
我们这里就点一下思路，因为这里不是我们要介绍的重点。但是这个思路会启发我们用单调栈去优化它。
我们在暴力枚举的时候，可以考虑枚举宽或者枚举高。
如果枚举宽，那就是两层for循环，第二层for循环向右走的时候记录所在高度的最小值，然后和宽度相乘，得到面积，然后取最大值。
我们给出参考代码：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int size = heights.size();
int ans = 0;
for (int left = 0; left < size; ++left) {// 枚举左边界
int Height = INT_MAX;
for (int right = left; right < size; ++right) {//从左边界开始，枚举右边界
Height = min(Height, heights[right]); // 确定高度
ans = max(ans, (right - left + 1) * Height);// 计算面积取最大
}
}
return ans;
}
};
如果枚举高，那就是从左向右遍历数组（也就是height数组），对于每一个height数组里的值，再分别向左向右去找，找到能构成矩形的最大的值。
给出参考代码：（由于比较简单，就不做过多赘述）
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int size = heights.size();
int ans = 0;
for (int i = 0; i < size; ++i) {// 枚举高
int height = heights[i];
int left = i, right = i;// 确定左右边界
while (left - 1 >= 0 && heights[left - 1] >= height) {//往左遍历，确定最小高度
--left;
}
while (right + 1 < size && heights[right + 1] >= height) {//往右遍历，确定最小高度
++right;
}
ans = max(ans, (right - left + 1) * height);// 计算面积，并取最大值
}
return ans;
}
};
我们可以看到，上述两种做法都是O(N^2)的做法，对于这种问题，如果被问道，那肯定是要求优化的。
那我们怎么优化呢？我们注意到，实际上在枚举高的时候，我们在外层循环只遍历了一次，而内层循环实际上就是在找左边最近较小值和右边最近较小值的过程。对于这样的需求，我们应当瞬间想到用单调栈。
我们同时也会发现，如果我们用单调栈来枚举高，那么这道题的时间复杂度就成功地变为了O(N)（因为每一个元素最多入栈和出栈各一次）
所以分析到这里，各位同学们也就能发现了，这道题的本质实际上就是找每一个数的左侧最近较小值和右侧最近较小值。本质就是单调栈问题。
我们来给出参考代码：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> stk;
int n = heights.size();
vector<int> left(n + 1,-1), right(n + 1,n); //开辟两个数组，分别记为左侧最小值和右侧最小值，相当于我们上面代码中将一个有两行的二维数组拆分成两个一维数组
for(int i = 0; i < n; i++) {
while(!stk.empty() && heights[stk.top()] >= heights[i]){//如果栈不为空，且栈顶元素更大
right[stk.top()] = i; //则栈顶元素的右侧较小值为i下标所对应的值
stk.pop(); //栈顶元素出栈
}
left[i] = stk.empty() ? -1 : stk.top(); //记录该元素左侧元素的最近较小值所对应的位置（要么就是栈顶元素下标所对应的值，要么为-1）
stk.push(i); //入栈
}
int Max = INT_MIN;
for(int i = 0; i < n; i++) { //遍历该数组的元素，并计算出面积的最大值
Max = max(Max, (right[i] - left[i] - 1)*heights[i]);
}
return Max;
}
};
这样以后，我们就达到了优化的效果。
实际上，本题和 接雨水 那道题相比还是比较容易的。但是凡是用到单调栈的地方，其核心、本质都是在干一件事情，也就是我们在文章当中反反复复强调的：找到元素的左侧最近最小（大）值和找到右侧的最近最小（最大）值。当然，有关单调栈，日后我们还会讲解更丰富的变形，敬请期待哈~~~~
第三题题解
（下题二维数组图）
有了单调栈的铺垫和第二题的基础，理解起来第三题就比较容易了。怎么说？具体往下看：
对于这样一个矩阵，我们可以看成是在两个维度上的柱状图。即我们可以这样认为：
在第一行，其是这样一个柱状图：
然后利用第二道题的原理，来去计算在这样一个视角下（实际上是只考虑第一行），所得矩形的最大面积。
同理，第二行我们可以认为其是这样一个柱状图：
然后和第一行干同样的事情——在这样一个视角下，取计算矩形的最大面积。
第三行....第n-1行同理即可，然后再最后的时候，去比较它们的面积最大值就行。
我们给出参考代码：（注：下面的参考代码是以每一列为一个视角，来去横向画柱状图的，其本质和上面的说法一样）（就是说，下面我写的代码在看柱状图的时候是要把头侧过来看的）
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int row = matrix.size(); //获得行数和列数
int col = matrix[0].size();
vector<vector<int>> nums(row, vector<int>(col, 0)); //开辟数组
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == '1') {
if (j == 0) nums[i][j] = 1;
else nums[i][j] += nums[i][j - 1] + 1; //用来计算每一列的height
}
}
}
int Max = INT_MIN;
for (int j = 0; j < col; j++) {//下面的做法就是用单调栈来去计算以每一列为视角的矩形面积的最大值，
//并求出这些最大值中的最大值
vector<int> left(row, -1), right(row, row);
stack<int> stk;
for (int i = 0; i < row; i++) {
while (!stk.empty() && nums[stk.top()][j] >= nums[i][j]) {
right[stk.top()] = i;
stk.pop();
}
left[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
for (int i = 0; i < row; i++) {
int width = right[i] - left[i] - 1;
Max = max(Max, width * nums[i][j]);
}
}
return Max;
}
};
OK，这样的话，我们就已经将这道题的包装层层拆解，然后求得了最终的答案。
第四题题解
乍一看，好像和单调栈有关系，因为经验告诉我们像这种带有括号的问题通常会用到栈，然后让左括号入栈，遇到右括号时去匹配一个左括号；
但是好像又没有关系，因为联想到单调栈的作用，我们并非找一个右括号的最近左括号呀....
实际上，本道题也是单调栈的变形，因为我们每完成一对括号的匹配，我们就pop出来一个左括号，实现一对匹配，这样的话，我们就能够得到括号的长度。
那问题又来了，按照上面的思路，我们对于“()()”这样的括号长度该怎么进行操作呢？
我们注意到一点，包括在前面的讲解当中也在渗透，我们有的时候，对一个栈pop后栈顶的元素也是比较关心的（如果栈为空，通常设为-1）。本道题也一样。
如果我们将一个和右括号匹配了的左括号pop出去后，这个时候，我们再来看栈顶元素，此时栈顶元素的下标 不正是开始匹配的左括号的下标 的 前一个位置吗？肯定啊！
那这样就好办了，我们只要在最后匹配结束的时候，看一下top()的下标是多少，然后用当前右括号的下标减去它，这样就可以清楚地计算出我们这个括号的长度是多少了。
然后我们在考虑一下边界条件：在一开始的时候，我们应当在栈底放上一个-1（便于配对第一对括号）。
那么我们现在来举个例子，即模拟这个出栈入栈的过程：
下面给出参考代码：
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
stk.push(-1); //在栈底放-1
int i = 0, size = s.size();
int maxx = 0;
while(i < size){
if(s[i] == '('){ //如果是左括号，就直接入栈
stk.push(i);
}
else{
stk.pop();
if(stk.empty()){//如果pop一个之后栈就为空，
//那么就代表着栈中原来只有一个'('或者')'，-1打底，
stk.push(i);//这个时候，我们直接将i push进去，类似于将i打底，
//表示着上一次匹配结束的括号字串的最右侧的括号
}
else{
maxx = max(maxx, i - stk.top());//如果不为空，那么就计算括号的长度，
//然后保留最大值
}
}
i++;
}
return maxx;
}
};
像这个的单调栈问题，实际上从本质上来说，都是解决的是：找最近的左和最近的右，或者利用单调栈的特点来去进行匹配操作。
我们首先是要去熟悉单调栈这种结构，熟悉后，我们遇到问题的时候就只需要将原来包装的问题拆分，层层拆分后发现有用单调栈的这种需求，便可以瞬间联想到并去使用。
好了，本节内容——单调栈的有关内容就介绍完毕啦，然后嘞，如果上文有什么说的不对的、或者是可以更好地，欢迎私信或评论进行指正吖~~~
在文末，我们附上LeetCode上有关单调栈的7道题目，感兴趣的小伙伴们可以试着练习几道哈~~~
接雨水 - 力扣（LeetCode）
每日温度 - 力扣（LeetCode）
最短无序连续子数组 - 力扣（LeetCode）
股票价格跨度 - 力扣（LeetCode）
去除重复字母 - 力扣（LeetCode）
移掉 K 位数字 - 力扣（LeetCode）
下一个更大元素 I - 力扣（LeetCode）
版权归原作者 jxwd 所有， 如有侵权，请联系我们删除。