【算法深练】单调栈：有序入栈，及时删除垃圾数据

目录

前言

记录下一个可能满足的位置

记录还没找到满足的位置

单调栈基础题热身

739. 每日温度

1475. 商品折扣后的最终价格

496. 下一个更大元素 I

503. 下一个更大元素 II

901. 股票价格跨度

853. 车队

单调栈进阶题目

1019. 链表中的下一个更大节点

654. 最大二叉树

456. 132 模式

3113. 边界元素是最大值的子数组数目

2866. 美丽塔 II

总结

前言

先通过一道题目看一下单调栈的出题角度。

记录距离下一个气温升高的天数，怎么求解？？？直接暴力就是O(N^2)肯定超时，有没有什么高效的方法；该类型题目有两种做法从右向左遍历或从左向右遍历，这两种解题思路有所差异，但是本质还是一样的。

记录下一个可能满足的位置

从右向左记录下一个温度升高的天数和温度。比如从右向左：

1. 走到3位置，[6]比起大找到了，3存起来[3,6]；
2. 走到2位置，[3,6]其中3比它大找到了，2存起来[2,3,6]；
3. 走到5时，[2,3,6]其前面的[2,3]比5小，因为有5的存在[2,3]没有必要再存储了，因为5前面的数不可能将[2,3]作为第一个比其温度大的位置，[2,3]删除，5进入[5,6]；
4. .........

一直这样进行下去即可。这种先将数据存储，再将数组删除的方式类似于栈的先将后出的模式，所以可以使用栈来模拟这个过程。

记录还没找到满足的位置

从左向右记录还不没有找到下一个温度升高的天数。

1. 1入栈，[1]；
2. 4比1大，所以1找到了满足条件的位置，1出栈，4入栈，[4]；
3. 3比4小，3入栈[3,4]；
4. 5比[3,4]都大，两个出栈，5入栈，[5]；
5. ........

一直处理到结束即可。

两种方法，不论是记录下一个可能满足条件的位置还是记录没有找到满足条件的位置，都是为了及时处理掉无用数据，让栈中的数据是有序的，所以被称为单调栈。

PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。

单调栈基础题热身

739. 每日温度

就是上面举例的题目，通过两种解法进行实现。

从右向左：

class Solution {public: vector dailyTemperatures(vector& nums) { //从右向左,维护下一个可能满足的位置 int n=nums.size(); stack<pair> st; //既要存放下标又要有温度 st.push({nums[n-1],n-1}); vector ret(n); for(int i=n-2;i>=0;i--) { while(!st.empty()&&st.top().first<=nums[i]) st.pop(); //如果栈顶元素小,出栈  if(st.empty()) ret[i]=0; //栈为空,没有满足的温度 else ret[i]=st.top().second-i; //栈不为空 st.push({nums[i],i}); //将当前位置加入到栈中 } return ret; }};

从左向右：

class Solution {public: vector dailyTemperatures(vector& nums) { //从左向右,维护还没有找到答案的位置 int n=nums.size(); stack<pair> st; st.push({nums[0],0}); vector ret(n,0); for(int i=1;ist.top().first) //如果nums[i]>top的值,说栈顶的元素找到答案了 { int index=st.top().second; ret[index]=i-index; st.pop(); } st.push({nums[i],i}); //将当前位置加入栈 } return ret; }};

1475. 商品折扣后的最终价格

从左向右：维护还没有找到满足的位置；

class Solution {public: vector finalPrices(vector& prices) { //从左向右,栈中记录还没有找到满足条件的数据 int n=prices.size(); stack<pair> st; st.push({prices[0],0}); vector ret(prices); //没有折扣的位置就是原价 for(int i=1;i=prices[i]) //将找到答案的出栈 { int index=st.top().second; ret[index]=st.top().first-prices[i]; st.pop(); } st.push({prices[i],i}); //当前位置入栈 } return ret; }};

从右往左：记录下一个可能满足的位置。

class Solution {public: vector finalPrices(vector& prices) { //从右往左,记录下一个可能满足条件的位置 int n=prices.size(); stack<pair> st; st.push({prices[n-1],n-1}); vector ret(prices); for(int i=n-2;i>=0;i--) { while(!st.empty()&&st.top().first>prices[i]) //在栈里面找满足条件的 st.pop(); if(st.empty()) ret[i]=prices[i]; //栈为空,没有满足条件的 else ret[i]=prices[i]-st.top().first; //栈不为空,栈顶为第一个满足条件的 st.push({prices[i],i}); } return ret; }};

496. 下一个更大元素 I

题解：单调栈。先将nums2中所有位置下一个更大元素存储起来，在遍历nums1即可。

从右向左：记录下一个可能满足条件的位置；

class Solution {public: vector nextGreaterElement(vector& nums1, vector& nums2) { //先将nums2中每个位置下一个更大元素记录下来 //从右往左：存储下一个可能满足条件的位置 int n1=nums1.size(),n2=nums2.size(); stack st; unordered_map m; //存储nums2中每一个位置的元素,方便nums1在nums2中的查找 st.push(nums2[n2-1]); m[nums2[n2-1]]=n2-1; vector next(n2,-1); for(int i=n2-2;i>=0;i--) { m[nums2[i]]=i;  while(!st.empty()&&st.top()<nums2[i]) st.pop(); //找满足条件的下一个位置 if(!st.empty()) next[i]=st.top(); st.push(nums2[i]); } vector ans(n1);  for(int i=0;i<n1;i++) { int index=m[nums1[i]]; //index是nums2中与nums1[i]相同的位置下标 ans[i]=next[index]; } return ans; }};

从左向右：存储还没找到满足条件的位置。 

class Solution {public: vector nextGreaterElement(vector& nums1, vector& nums2) { //先将nums2中每个位置下一个更大元素记录下来 //从左向右：存储还没找到满足条件的位置 int n1=nums1.size(),n2=nums2.size(); stack<pair> st; unordered_map m; //存储nums2中每一个位置的元素,方便nums1在nums2中的查找 st.push({nums2[0],0}); m[nums2[0]]=0; vector next(n2,-1); for(int i=1;i<n2;i++) { m[nums2[i]]=i;  while(!st.empty()&&st.top().first<nums2[i]) //将找到满足条件的位置出栈 { int index=st.top().second; next[index]=nums2[i]; st.pop(); } st.push({nums2[i],i}); //入栈 } vector ans(n1);  for(int i=0;i<n1;i++) { int index=m[nums1[i]]; //index是nums2中与nums1[i]相同的位置下标 ans[i]=next[index]; } return ans; }};

503. 下一个更大元素 II

题解：单调栈，需要进行循环搜索。实际上就是遍历两边数组即可。下面贴从左向右的代码实现。

class Solution {public: vector nextGreaterElements(vector& nums) { //进行两次单调栈 int n=nums.size(); stack<pair> st; //从前往后,存储还没有找到满足条件的位置 st.push({nums[0],0}); vector ret(n,-1); for(int i=1;i<2*n;i++) { while(!st.empty()&&st.top().first<nums[i%n]) //将找到满足条件的位置出栈 { int index=st.top().second%n; ret[index]=nums[i%n]; st.pop(); } st.push({nums[i%n],i%n}); } return ret; }};

901. 股票价格跨度

题解：单调栈。返回股票当日价格的跨度，就是向前找第一个大于今日的日期。

class StockSpanner { int dayi; stack<pair> st;public: StockSpanner() { dayi=0; } int next(int price) { //向前找,找第一个大于今天的位置 dayi++; //天数+1 while(!st.empty()&&st.top().firstnext(price); */

853. 车队

题解：此题直接看不太好想，但是如果画个图就很清晰。

维护一个单调栈，从左向右栈在递减，最终栈中剩余的元素就是车队的数量。

class Solution {public: int carFleet(int target, vector& position, vector& speed) { int n=position.size(); //要先将车队的位置进行从左到右的排列 vector<pair> tmp(n);  for(int i=0;i<n;i++) tmp[i]={position[i],speed[i]}; sort(tmp.begin(),tmp.end()); //存储每个车达到终点需要花费的时间 vector nums(n); for(int i=0;i<n;i++) nums[i]=(target-tmp[i].first)/(double)tmp[i].second; //进行单调栈 stack st; for(int i=0;i<n;i++) { while(!st.empty()&&st.top()<=nums[i]) st.pop(); //如果靠近终点的车需要的时间更长,后面的车就能追上形成车队 st.push(nums[i]); } return st.size(); }};

单调栈进阶题目

1019. 链表中的下一个更大节点

题解：单调栈。此题仅仅是将数组换成了链表而已。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public: vector nextLargerNodes(ListNode* head) { //因为是链表,所以从前往后遍历更方便,记录还没有找到答案的数据 stack<pair> st; int n=0,i=0; ListNode* cur=head; while(cur) //统计链表的长度 { cur=cur->next; n++; } vector ret(n,0); cur=head; while(cur) { while(!st.empty()&&st.top().firstval) //将栈中前面的数据进行更新 { int index=st.top().second; ret[index]=cur->val; st.pop(); } st.push({cur->val,i}); i++; cur=cur->next; } return ret; }};

654. 最大二叉树

解法一：递归造树。根据题目写递归条件即可。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution { //使用递归来完成 TreeNode* func(vector& nums,int left,int right) { if(right<left) return nullptr; int pos=left; for(int i=left;i<=right;i++) //找最大值 if(nums[pos]left=func(nums,left,pos-1); //创建左树 root->right=func(nums,pos+1,right); //创建右树 return root; }public: TreeNode* constructMaximumBinaryTree(vector& nums) { return func(nums,0,nums.size()-1); }};

 上面在找最大值的时候每一次都要遍历，太慢了。能不能进行以下优化。

根据上面的方式，好像有一些规律了，两个数之间大于的在上面，小于的在下面，具体是在左树还是右树取决于在数组中的前后顺序。
那如果要具体查找一个数字的存放位置，只需要确定其父节点嘛，因为是从左往右遍历，所以如果父节点在前面当前节点一定是父节点右树，如果父节点在右边那一定是父节点的右树，所以可以使用一个单调栈来存储可能是父节点的位置。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: TreeNode* constructMaximumBinaryTree(vector& nums) { //使用单调栈来存储可能是父节点的位置 int n=nums.size(); vector tmp(n); stack st; //存放可能是父节点的位置 int ret=0; //ret记录最大值的位置,返回值就是最大值对应的节点 for(int i=0;inums[ret]) ret=i; TreeNode* cur=new TreeNode(nums[i]); while(!st.empty()&&st.top()->valleft=st.top(); //数组顶部更小,一定不是nums[i]的父节点,一定在nums[i]的左树上 st.pop(); } if(!st.empty()) st.top()->right=cur; //找到比他大的位置,其就是它的父节点 tmp[i]=cur; st.push(cur); } return tmp[ret]; }};

456. 132 模式

方法一：枚举j位置，先左找最小值O(1)，向右找比nums[i]大的第一个数O(logN)。右边可以使用一个multiset维护，用upper_bound找第一个大于nums[i]的位置。

class Solution {public: bool find132pattern(vector& nums) { //枚举中间位置j,向两边找满足条件的位置 //维护找j左边的最小值O(1) //在j右边找比左边最小值大的位置,可以使用set存储右边的值,查找就是O(logN) int n=nums.size(); multiset rs; //不能使用set for(int i=2;i<n;i++) rs.insert(nums[i]); int lmin=nums[0]; for(int i=1;ilmin) { auto it=rs.upper_bound(lmin); if(it!=rs.end()&&*it<nums[i]) return true; } lmin=min(lmin,nums[i]); rs.erase(rs.find(nums[i+1])); //只删除rs中的一个nums[i] } return false; }};

 枚举j向两边进行查找，查找左边时间为O(1),但是查找右边需要O(logN)，能否进行优化？？？

如果枚举i，能不能直接找到j和k使结果满足条件；能否只维护一个数就能直接找到另外一个数>据？？

先说解法：从后往前枚举i，维护一个单调递减的栈，用k记录从栈中pop的最大值，如果k<nums[i]就说明存在满足条件的。
解释：枚举i不用多说，如果我们想找j和k，因为nums[i]<nums[k]<nums[j]所以nums[k]和nums[j]越大越有可能满足条件，所以维护一个单调递减的栈，如果栈pop了就说明存在nums[k]<nums[j]，找nums[k]的最大值才能更大可能使得nums[i]<nums[k]。== 

class Solution {public: bool find132pattern(vector& nums) { int n=nums.size(),k=INT_MIN; //k来记录栈中删除元素的最大值 if(n<3) return false; stack st({nums[n-1]}); if(nums[n-2]>nums[n-1]) //将最后两个元素放入栈 { k=max(k,st.top()); st.pop(); } st.push(nums[n-2]); for(int i=n-3;i>=0;i--) { if(nums[i]<k) return true; //如果nums[i]<nums[k]一定存在满足条件的,因为栈中存在大于nums[k]的数据 while(!st.empty()&&st.top()<nums[i]) //维护单调递减栈 { k=max(k,st.top()); st.pop(); } st.push(nums[i]); } return false; }};

3113. 边界元素是最大值的子数组数目

题目很简单，但是要如何处理，直接进行枚举左，找右时间复杂度为O(N^2)超时；

根据根据题目分析，如果数据是[4,3,2,1,2,1]当遍历到最后一个1的时候，它是不能与前面一个1组成子数组的，所以前面的1属于垃圾数据，不应该存在，将1删除后，数组就是有序的，那么只有是有序的时候才能满足条件，删除垃圾数据也是从左往右进行删除的，那不就是单调栈模型嘛。

细节：在进行数据个数统计的时候，如果栈中是[3，3，3，3]就需要依次将栈中的元素删除太麻烦了，可以直接使用stack<pair>既存储元素，也存储元素的个数。

class Solution {public: long long numberOfSubarrays(vector& nums) { int n=nums.size(); stack<pair> st; long long ret=n; //向将子数组长度为1的加入到答案中 for(int i=0;i<n;i++) { while(!st.empty()&&st.top().first<nums[i]) st.pop(); //如果栈顶元素小,出栈 if(!st.empty()&&st.top().first==nums[i]) //栈顶与当前元素相等,是满足条件的子数组 { ret+=st.top().second; st.push({nums[i],st.top().second+1}); }  else st.push({nums[i],1}); } return ret; }};

2866. 美丽塔 II

山脉数组满足中间高两边地,可以对山脉进行消减,找出高度和的最大值
枚举所有位置作为山顶,看左右两边的高度和.通过这种方式时间复杂度为O(N^2)超时
能否进行优化???

对于左半部分是单调递增的，对于右半部分是单调递减的。是不是可以对左右两半部分分开处理，再进行整合，先从右往左求出每个位置右半部分的和；再从左向右求出每个位置左半部分的和；最后再进行整合。
核心：左右两边操作类似，将左右两边分开处理，否则处理起来不方便 ；

那要如何统计左右两边的数据呢？？？数据要满足单调的条件，所以可以使用一个单调栈来实现
细节：如果栈中有大量重复数据，可以使用下标来记录从那个位置开始是什么数据，这样在进行pop的时候更高效。

class Solution { typedef long long LL;public: long long maximumSumOfHeights(vector& nums) { int n=nums.size(); vector right(n+1); //统计右边从i位置向右的高度和 vector left(n+1); //统计从i位置向左数据和 stack<pair> st; //使用pair来存储下标位置以及元素大小,存储下标方便对数据进行修改 st.push({0,n}); //先放入一个元素,将n作为一个哨兵位,再使用i-x的时候更方便 LL sum=0; for(LL i=n-1;i>=0;i--) //统计右边和 { while(!st.empty()&&st.top().first>nums[i]) { auto [x,y]=st.top(); st.pop(); sum-=x*(st.top().second-y); } sum+=(st.top().second-i)*nums[i]; st.push({nums[i],i}); right[i]=sum; } while(!st.empty()) st.pop(); //统计左边和 st.push({0,-1}); sum=0; for(LL i=0;inums[i]) { auto [x,y]=st.top(); st.pop(); sum-=x*(y-st.top().second); } sum+=(i-st.top().second)*nums[i]; st.push({nums[i],i}); left[i]=sum; } LL ret=0; for(LL i=0;i<n;i++) //求最大值 ret=max(ret,left[i]+right[i]-nums[i]); return ret; }};

总结

单调栈的题目特点还是很明显的：要对无用数据进行删除，删除后其他数据呈现单调的趋势就是单调栈。单调栈难题在实现起来有些很复杂，所以应当先考虑化繁为简，先局部在整体，将题目分解开。