一命通关单调栈

---

前言

我们只是卑微的后端开发。按理说，我们是不需要学这些比较进阶的算法的，可是，这个世界就是不讲道理。最开始，想法是给leetcode中等题全通关，我又不打ACM我去天天钻研hard干嘛，于是碰见单调栈树状数组的题目就pass。可是不说大厂，现在中厂也会考你hard算法你又不乐意。没办法，笔试全挂颓废了一个多星期之后，还是决定把进阶一点的算法问题更完，也当算法生涯不留遗憾了。

---

朴素单调栈

光头强追熊二

假如，狗熊岭有一群熊二。先别管为什么会出现这么多熊二，反正熊二太多把光头强整急眼了，光头强拿起枪追着一群熊二跑。

我们用一个数组来表示不同熊二的身高，数组最后一个值为枪管的高度：

vector<double> height = {1.8 , 2.1 , 1.75 , 1.5 , 1.65};

假如我只开一枪，不考虑子弹很nb可以穿透，问，这一枪会打到哪一个熊二？

问题分析

• 如果熊二比枪管矮，那么这一枪肯定打不到他，直接排除。

• 如果熊二比枪管高，那么这一枪一定会打到他吗？不一定。因为如果前面有熊二给他挡枪了，那么也是打不到的。

我们要找的熊二，是第一个不会被其他熊挡枪的熊二。不会被其他熊挡枪，意思就是前面一定不会出现比枪管高的熊。所以，我们实际要找的，是枪管左边第一个比枪管高的熊。

转化成程序问题，就是找数组最后一个数(因为最后一个数是枪管高度)，左边第一个大于其的数。

问题解决

相信就算是一个初学者，都可以轻易解决这个问题。我们只要从数组最后一个数开始，遍历整个数组，找到第一个大于目标值的数就可以了。

vector<double> height = {1.8 , 2.1 , 1.75 , 1.5 , 1.65};
int size = height.size();int target = -1;//-1代表一个熊也打不到for(int i = size - 1;i >= 0;i--)
{if(height[i]>height[size-1]){target = i;break;}
}

光头强追光头强

现在，狗熊岭没有熊二了，可是出现了一堆光头强。每个光头强手上都有枪，假如每个光头强都是便太砂仁饭，

问，如果每个光头强都把枪举到头顶往前开一枪，那么每个光头强会打到谁？

问题分析

和上一个问题一样。因为每个光头强都把枪举过头顶了，所以我们要求的是每个光头强，左边第一个比他高的人。

我们还是用一个数组来表示他们的身高：

vector<double> height = {1.8 , 1.6 , 1.3 , 2.1 , 1.4};

也就是求每个元素，左边第一个大于其的元素。

问题解决

拿到这个问题很简单：一个元素我们会求，那所有元素，嵌套一个循环不就好了！

vector<double> height = {1.8 , 2.1 , 1.75 , 1.5 , 1.65};
int size = height.size();vector<int> target(size,-1);//-1代表打不到，其他表示找到元素的下标for(int loop = 0;loop < size;loop++)
{for(int i = loop;i >= 0;i--){if(height[i]>height[loop]){target[loop] = i;break;}}
}

可是，这个时间复杂度是典型的O(N^2)

有的兄弟有的。

问题优化

当我们要求某一个位置左侧第一个大于其的元素时，要遍历的是这个元素左侧的所有值：

然后，对所有元素，我们是从左往右遍历过来的，即：

1. 先求下标为0的答案

2. 再求下标为1的答案，遍历0

3. 再求下标为2的答案，遍历0~1

4. 再求下标为3的答案，遍历0~2

5. ...

我们可以发现，我们要遍历的元素，其实是我们已经访问过的。我们可以单开一个数组，来表示每一次需要遍历的元素：

vector<double> height = {1.8 , 2.1 , 1.75 , 1.5 , 1.65};
int size = height.size();vector<int> traverse;//每一个位置需要遍历的元素
vector<int> target(size,-1);//-1代表打不到，其他表示找到元素的下标for(int loop = 0;loop < size;loop++)
{for(int i = traverse.size()-1;i>=0;i--){if(height[traverse[i]]>height[loop]){target[loop] = traverse[i];break;}}//当遍历到这个元素时，后面的所有元素在寻找答案时都会遍历到这个元素，我们就把这个元素的位置插入到数组中traverse.push_back(loop);
}

我们来看看这个traverse数组的特点：

假如我们height数组长这样：

 

1. 循环到0时，左侧没有元素，不管。然后把0插入到traverse数组中

2. 循环到1时，遍历traverse数组(0~0)，找到了11这个元素比当前位置9大，于是把11的下标0插入到结果数组target中。然后把1插入到traverse数组中

3. 循环到2时，遍历traverse数组(0~1)，没有找到比当前位置13更大的数，于是不管。然后把2插入到traverse数组中

4. 循环到3时，遍历traverse数组(0~2),首先就找到了13，发现当前位置比15小。按理说，我们是应该继续往前找的，可是，我们真的需要往前找吗？我们刚刚已经知道了，13前面都没有比13更大的数了，自然13前面也没有比15更大的数。所以，遍历到13我们就可以终止了，然后得到结论——左边没有比15更大的数。

所以，我们可以得到一个优化方法：

当遍历到左边元素的最大值时，如果还没有找到答案，我们可以立即终止，然后得到结论——左边没有比他更大的元素。而这个最大值，我们可以用一个数字来表示，随时更新：

vector<double> height = {11，9，13，15，10，20，3};
int size = height.size();vector<int> traverse;//每一个位置需要遍历的元素
int leftMax = 0;//左边最大元素的位置vector<int> target(size,-1);//-1代表打不到，其他表示找到元素的下标for(int loop = 0;loop < size;loop++)
{for(int i = traverse.size()-1;i>=0;i--){if(height[traverse[i]]>height[loop]){target[loop] = traverse[i];break;}if(i == leftMax)break;}//当遍历到这个元素时，后面的所有元素在寻找答案时都会遍历到这个元素，我们就把这个元素的位置插入到数组中traverse.push_back(loop);//如果当前元素比左边最大元素大，那么更新最大元素if(height[loop] >= height[leftMax])leftMax = loop;
}

我们知道了一次循环的终止条件。可是，假如我们循环到了3，要遍历0~2，我们一定要从2开始，判断2，判断1，再判断0吗？我们可不可以，优化一下遍历的顺序呢？

假如我们的height数组变成了这样：

明显的先减后增。而因为左边最大元素在下标0，所以刚刚的优化等于没优化。

• 但是，当我们遍历到下标4即元素16时，我们一直往前找，找到了下标1，于是target[4] = 1;

• 我们遍历到下标5即18时，往前找找到了16，不是想要的答案。正当我们想继续往前一个一个找的时候，16叫住了我们，说道：

"我刚刚已经找过了，2~3都比我小，你不用再找2~3了。"

所以，当我们实际开始找时，找到了16，不是我们要的答案。我们探寻其下标，发现左边第一个比他大的元素是下标1，即2~3都比它小。所以2~3我们就不找了，直接跳到1开始继续往前遍历。

此时，我们又得到了另一个优化算法：

 当我们往前遍历到下标i时，会有两种情况：

1. height[i] > height[loop]，i就是我们要找的答案，target[loop] = i，循环终止

2. height[i] < height[loop]，i不是我们要找的答案

而当i不是我们要找的答案时，又会分为两种情况：

1. target[i] == -1，i前面所有元素都比它小，那肯定也比height[loop]小，故前面没有答案，循环终止

2. target[i] == j，下标j是i前面第一个比它大的元素。那么j+1~i肯定都不会是答案，我们直接跳到下标j继续遍历

 用代码表示：

vector<double> height = {11，9，13，15，10，20，3};
int size = height.size();vector<int> traverse;//每一个位置需要遍历的元素
vector<int> target(size,-1);//-1代表打不到，其他表示找到元素的下标for(int loop = 0;loop < size;loop++)
{for(int i = traverse.size()-1;i>=0;)//就不要i--了，因为他自己会一直往前跳{if(height[traverse[i]]>height[loop]){target[loop] = traverse[i];break;}else{if(target[i]==-1)break;elsei=target[i];}}//当遍历到这个元素时，后面的所有元素在寻找答案时都会遍历到这个元素，我们就把这个元素的位置插入到数组中traverse.push_back(loop);
}

代码优化

因为，每当遍历到下标i时，如果是答案，遍历就终止了；如果不是答案，那么一定会跳转到下标j。此时，我们是不是可以认为，j+1~i-1这一段元素，一定永远不会被遍历到，那么他们就可以从traverse数组当中滚蛋？

比如这个数组，当遍历到下标4时，要么height[loop]比他小下标4就是答案遍历终止，要么height[loop]比他大会跳转到下标1，下标2~3永远不会被遍历到，那么下标2~3就可以从traverse数组中删除了。此时traverse数组中剩下的，就都是会被遍历到的下标，即[0,1,4]，用代码表示：

vector<double> height = {11，9，13，15，10，20，3};
int size = height.size();vector<int> traverse;//每一个位置需要遍历的元素
vector<int> target(size,-1);//-1代表打不到，其他表示找到元素的下标for(int loop = 0;loop < size;loop++)
{for(int i = traverse.size()-1;i>=0;i--){if(height[traverse[i]]>height[loop]){target[loop] = traverse[i];break;}}//如果traverse中，最后一个下标代表的元素比当前元素还小，那么最后一个下标一定不会被遍历到，我们就把他删除掉//一直删除下去，剩下的最后一个元素，就是target[loop]while(!traverse.empty()&&height[traverse.back()]<height[loop]){traverse.pop_back();}//然后把当前元素下标插入进去traverse.push_back(loop);
}

这样操作之后，我们会发现，traverse数组会有两个特点：

1. traverse数组中最后一个下标代表的元素一定小于倒数第二个下标代表的元素，即traverse数组下标代表的元素是单调递减的。

2. traverse数组只对最后一个元素进行操作(删除和插入)，即traverse数组其实是一个栈。

所以，这样的traverse数组，我们就给他取了一个名字——单调栈。

---

朴素单调栈

单调栈，解决最直接的问题就是——

找到每一个元素 左边/右边 第一个 大于/小于 其的元素

来看题目：496. 下一个更大元素 I - 力扣（LeetCode）

这不就是刚刚说到的问题吗，只不过从找左边，变成了找右边。那解决问题的区别是什么？loop从左往右，变成了loop从右往左。

而刚刚说到，traverse其实就是一个栈，那我们试试用栈来解决。

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {stack<int> traverse;vector<int> target(nums2.size(),-1);for(int loop = nums2.size()-1;loop>=0;loop--){//如果traverse最后一个元素比他小，那么最后一个元素一定不会被遍历到，直接删除//这里，我们只是把遍历和删除放在了一起，因为删除该元素然后再访问最后一个元素，不就是i--吗？while(!traverse.empty()&&nums2[traverse.top()]<nums2[loop]){traverse.pop();}if(!traverse.empty())target[loop] = traverse.top();traverse.push(loop);}}

而根据题目的要求，我们只需要再用一个哈希表就能完成了，简略带过：

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {stack<int> traverse;vector<int> target(nums2.size(),-1);for(int loop = nums2.size()-1;loop>=0;loop--){while(!traverse.empty()&&nums2[traverse.top()]<nums2[loop]){traverse.pop();}if(!traverse.empty())target[loop] = traverse.top();traverse.push(loop);}unordered_map<int,int> hash;for(int i = 0;i < nums2.size();i++){hash[nums2[i]] = target[i]==-1?-1:nums2[target[i]];}vector<int> ans(nums1.size());for(int i = 0;i<nums1.size();i++){ans[i] = hash[nums1[i]];}return ans;}

所以，我们就获得了解题公式：

左边第一个更大的元素

从左往右遍历，维护一个递减单调栈：

vector<int> preGreaterElement(vector<int>& nums) {stack<int> traverse;vector<int> target(nums.size(),-1);for(int loop = 0;loop<nums.size();loop++){while(!traverse.empty()&&nums[traverse.top()]<nums[loop]){traverse.pop();}if(!traverse.empty())target[loop] = traverse.top();traverse.push(loop);}return target; }

右边第一个更大的元素

从右往左遍历，维护一个递减单调栈：

vector<int> nextGreaterElement(vector<int>& nums) {stack<int> traverse;vector<int> target(nums.size(),-1);for(int loop = nums.size()-1;loop>=0;loop--){while(!traverse.empty()&&nums[traverse.top()]<nums[loop]){traverse.pop();}if(!traverse.empty())target[loop] = traverse.top();traverse.push(loop);}return target; }

左边第一个更小的元素

从左往右遍历，维护一个递增的单调栈
(道理一样，可以自己想想)

vector<int> preLessElement(vector<int>& nums) {stack<int> traverse;vector<int> target(nums.size(),-1);for(int loop = 0;loop<nums.size();loop++){while(!traverse.empty()&&nums[traverse.top()]>nums[loop]){traverse.pop();}if(!traverse.empty())target[loop] = traverse.top();traverse.push(loop);}return target; }

右边第一个更小的元素

从右往左遍历，维护一个递增的单调栈

vector<int> nextLessElement(vector<int>& nums) {stack<int> traverse;vector<int> target(nums.size(),-1);for(int loop = nums.size()-1;loop>=0;loop--){while(!traverse.empty()&&nums[traverse.top()]>nums[loop]){traverse.pop();}if(!traverse.empty())target[loop] = traverse.top();traverse.push(loop);}return target; }

---

单调栈变种问题

删除k个元素的最小值

402. 移掉 K 位数字 - 力扣（LeetCode）

删掉k个元素，求剩下的最 大/小 值，其实有有一个相同的解法——单调栈。有人可能会问：

打个比方，1433223，删掉2个数字。我们期望删除的元素，有两个特点：

1. 尽量大

2. 尽量靠前

也就是，要把靠前的元素，删掉尽量大的。那怎么去定义这个尽量大呢？

假如返回值我们用一个数组来表示。

1. 刚开始，1加入数组，然后4加入数组。那这个1该不该删？直觉告诉我们，肯定不该删，因为1很小。4该不该删？不知道，因为我们还不清楚什么是尽量大

2. 然后，3加入数组了。那4该不该删？该删！因为4更靠前，而且4更大，这两个条件都满足了，那肯定是我们希望删除的元素。

3. 又来一个3加入数组。这个3该不该删？不知道，因为他们是相同的，肯定不满足尽量大这个条件。

4. 然后，2加入数组。和4一样，这下3更靠前而且更大，3就应该被删掉。

5. 但是，删掉一个3之后，还有第二个3。此时，我们已经删掉两个元素了，再删就多了，所以13223就是我们需要的答案。

而刚刚的流程，用一句话表示：

维护一个递增的单调栈，一直到删除k个元素为止

怎么证明这个方法的正确性呢？

假如一个数字序列abcde...，想删掉一个，我们只考虑第一个位置a，会得到两张情况：

1. 删掉a，序列变成bcde....

2. 不删a，改为从后面随机删一个，序列变成abcde...

那么判断哪个更大，一定要先判断首位的大小。

• 如果a大，那么abcde...一定大于bcde....

• 如果a小，那么abcde...一定小于bcde....

• 如果相等，那么就判断下一位

所以，删不删a，实际上就是先比较a和b哪个更大，如果a>b，那么a一定要被删掉，得到的结果才是更小的。  

代码：

string removeKdigits(string num, int k) {vector<char> stk;for (auto& digit: num) {while (stk.size() > 0 && stk.back() > digit && k) {stk.pop_back();k -= 1;}stk.push_back(digit);}for (; k > 0; --k) {stk.pop_back();}string ans = "";bool isLeadingZero = true;for (auto& digit: stk) {if (isLeadingZero && digit == '0') {continue;}isLeadingZero = false;ans += digit;}return ans == "" ? "0" : ans;}

思考

如果题目问你，保留k个数字，得到最小结果呢？

实际上就是，删掉n-k个数字，得到最小结果，不多赘述。

扩展阅读

这类题的方法，是从leetcode一个大佬题解中学来的，大家可以相信看看这位大佬的文章：

402. 移掉 K 位数字 - 力扣（LeetCode）402. 移掉 K 位数字 - 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 示例 1 ：输入：num = "1432219", k = 3输出："1219"解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。示例 2 ：输入：num = "10200", k = 1输出："200"解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。示例 3 ：输入：num = "10", k = 2输出："0"解释：从原数字移除所有的数字，剩余为空就是 0 。 提示： * 1 <= k <= num.length <= 105 * num 仅由若干位数字（0 - 9）组成 * 除了 0 本身之外，num 不含任何前导零https://leetcode.cn/problems/remove-k-digits/solutions/290203/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-5

---

右边最后一个更大的元素

962. 最大宽度坡 - 力扣（LeetCode）

这个题目最优解法并非这个。但是，为了说明共性解，我还是按照最共性的解法去说。

这个题目的问题，实际上就是，找到每个元素右边最后一个更大的元素，然后返回target[i]-i的最大值。

这类题目的解法：

1. 对数组中每一个元素，组成pair对

pair<int,int> p={val,pos};vector<pair<int,int>> pairs(nums.size());for(int i = 0;i < nums.size();i++)
{pairs[i] = {nums[i],i};
}

2. 将pair对按照val的大小排序

vector<pair<int,int>> pairs(nums.size());sort(pairs.begin(),pairs.end(),[](const pair<int,int>& p1,const pair<int,int>& p2){if(p1.first == p2.first)return p1.second < p2.second;return p1.first < p2.first;
});

 3. 排序好后，当前下标i右边的所有元素都比他大。而我们要找最远的，即找pos最大的那一个，问题就转变成为了:

找到排序好的数组中，下标为i的元素的右边某个元素j，使得pairs[j].second最大并且pairs[j].second>pairs[i].second

而这就是典型的问题，从右往左遍历，用单个变量记录最大值便可：

int maxPos = -1;vector<int> target(nums.size(),-1);for(int i = pairs.size()-1;i >= 0;i--)
{//没有考虑数组中有重复值if(pairs[i].second<maxPos){target[pairs[i].second] = maxPos;}else{maxPos = pairs[i].second;}
}
//最后得到的target数组，就是每个位置右边最后一个更大元素的下标

 4. 我们要求的，是target[i]-i的最大值，即遍历target数组找最大值

int ans = 0;
for (int i = 0; i < nums.size(); i++) {ans = max(ans, target[i] - i);
}return ans;

结合起来：

int maxWidthRamp(vector<int>& nums) {vector<pair<int, int>> pairs(nums.size());for (int i = 0; i < nums.size(); i++) {pairs[i] = {nums[i], i};}sort(pairs.begin(), pairs.end(),[](const pair<int, int>& p1, const pair<int, int>& p2) {if (p1.first == p2.first)return p1.second < p2.second;return p1.first < p2.first;});int maxPos = -1;vector<int> target(nums.size(), -1);for (int i = pairs.size() - 1; i >= 0; i--) {// 没有考虑数组中有重复值if (pairs[i].second < maxPos) {target[pairs[i].second] = maxPos;} else {maxPos = pairs[i].second;}}int ans = 0;for (int i = 0; i < nums.size(); i++) {ans = max(ans, target[i] - i);}return ans;}

---

右边小于其的最大元素

456. 132 模式 - 力扣（LeetCode）

 

同样，这个题目最优解法并非这个。但是，为了说明共性解，我还是按照最共性的解法去说。

这个题目要寻找的，是每个元素右边小于其的最大元素下标i与左边小于其的最小元素下标j，并让nums[i]<nums[j]

第一个问题简单，只需要遍历的时候用一个变量记录。第二个问题就有些困难，怎么找到右边小于其的最大元素呢？

这类题目的解法，还是依赖排序：

1. 对数组中每一个元素，组成pair对

pair<int,int> p={val,pos};vector<pair<int,int>> pairs(nums.size());for(int i = 0;i < nums.size();i++)
{pairs[i] = {nums[i],i};
}

2. 将pair对按照val的大小排序

vector<pair<int,int>> pairs(nums.size());sort(pairs.begin(),pairs.end(),[](const pair<int,int>& p1,const pair<int,int>& p2){if(p1.first == p2.first)return p1.second > p2.second;return p1.first > p2.first;
});

3. 排序好后，当前下标i右边的所有元素都比他小。而我们要从中找到找最大的，因为是降序排列，最近的肯定最大。可是最近一定满足条件吗？不一定，因为最近的可能在nums[i]的左边。所以，我们又要最近，又要使得pairs[i].second<pairs[j].second,那么问题就转变成了：

现在只看pairs的second形成一个新的数组pos

vector<int> pos(nums.size());for(int i = 0;i < nums.size();i++)
{pos[i] = pairs[i].second;
}

对pos数组，找到右边第一个更大的元素

那问题就简单了，从右往左遍历，维护一个递减单调栈：

vector<int> nextGreaterElement(vector<int>& nums) {stack<int> traverse;vector<int> target(nums.size(),-1);for(int loop = nums.size()-1;loop>=0;loop--){while(!traverse.empty()&&nums[traverse.top()]<nums[loop]){traverse.pop();}if(!traverse.empty())target[loop] = traverse.top();traverse.push(loop);}return target; }

 4. 题目要求的，是满足一个就返回true，那我们就从0开始遍历，维护最小值，发现满足条件就返回true就行

int minVal = nums[0];for(int i = 0;i < nums.size();i++)
{if(target[i]!=-1&&nums[target[i]]>minVal)return true;minVal = min(minVal,nums[i]);
}return false;

 结合起来：

vector<int> nextGreaterElement(vector<int>& nums) {stack<int> traverse;vector<int> target(nums.size(), -1);for (int loop = nums.size() - 1; loop >= 0; loop--) {while (!traverse.empty() && nums[traverse.top()] < nums[loop]) {traverse.pop();}if (!traverse.empty())target[loop] = traverse.top();traverse.push(loop);}return target;}bool find132pattern(vector<int>& nums) {vector<pair<int, int>> pairs(nums.size());for (int i = 0; i < nums.size(); i++) {pairs[i] = {nums[i], i};}sort(pairs.begin(), pairs.end(),[](const pair<int, int>& p1, const pair<int, int>& p2) {if (p1.first == p2.first)return p1.second > p2.second;return p1.first > p2.first;});vector<int> pos(nums.size());for (int i = 0; i < nums.size(); i++) {pos[i] = pairs[i].second;}vector<int> tmp = nextGreaterElement(pos);//这个地方可能有点绕，画图理解一下vector<int> target(nums.size(),-1);for(int i = 0;i<nums.size();i++){if(tmp[i]!=-1)target[pos[i]] = pos[tmp[i]];}int minVal = nums[0];for (int i = 0; i < nums.size(); i++) {if (target[i] != -1 && nums[target[i]] > minVal)return true;minVal = min(minVal, nums[i]);}return false;}

---

习题集

关于习题集这部分，其实没有习题集。leetcode上单调栈也就72题(其中还有一堆会员题)，给单调栈的题目一顺做下去就好了，再怎样也逃离不出这几种问题。

单调栈更多是一种优化方法，把O(N^2)的解法优化成O(NlogN)甚至O(N)。所以什么时候想到单调栈？不是刚开始拿到题目就说，哦我要维护一个单调栈；而是在暴力解法的时候发现，啊，我这样超时了，那我要优化一下，哦！这是一个单调栈问题，可以用单调栈优化！

---