4.20刷题记录（单调栈）

第一部分：简单介绍

单调栈我的理解是在栈中存储数字出现的位置，然后通过遍历比较当前栈顶元素与当前元素的大小关系，从而确定逻辑相关顺序。

第二部分：真题讲解

（1）739. 每日温度 - 力扣（LeetCode）

解题思路：在栈中存储每日的下标。如果当前元素大于栈顶元素，那么符合题意，就需要接下来的弹出以及赋值操作。如果小于等于则进行压栈。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int>stack;int n=temperatures.size();vector<int>ans(n,0);stack.push(0);for(int i=1;i<temperatures.size();i++){while(stack.empty()==0&&temperatures[i]>temperatures[stack.top()]){int a=stack.top();stack.pop();ans[a]=i-a;}stack.push(i);}return ans;}
};

（2）496. 下一个更大元素 I - 力扣（LeetCode）

解题思路：首先对数组2进行单调栈构建，然后将其存储到map中，避免两次遍历n^2的时间复杂度。然后通过map直接寻找即可。

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int>dict(nums2.size(),-1);vector<int>ans;stack<int>stack;for(int i=0;i<nums2.size();i++){while(stack.empty()==0&&nums2[i]>nums2[stack.top()]){int a=stack.top();stack.pop();dict[a]=nums2[i];}stack.push(i);}unordered_map<int,int>cnt;for(int i=0;i<nums2.size();i++){cnt[nums2[i]]=dict[i];}for(int i=0;i<nums1.size();i++){ans.push_back(cnt[nums1[i]]);}return ans;}
};

（3）503. 下一个更大元素 II - 力扣（LeetCode）

本题思路：与上一题类似，但是不同的是必须有一个循环。那么循环需要考虑模运算。这里只需要加一个入栈的条件即可，即stack.empty()||(i%n)!=stack.top()

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {//1.准备vector<int>dict(nums.size(),-1);stack<int>stack;int n=nums.size();//2.开始构建单调栈for(int i=0;i<nums.size()*2;i++){while(stack.empty()==0&&nums[i%n]>nums[stack.top()]){int a=stack.top();stack.pop();dict[a]=nums[i%n];}if(stack.empty()||(i%n)!=stack.top()){stack.push(i%n);}            }//3.outputreturn dict;}
};

（4）42. 接雨水 - 力扣（LeetCode）

思路一：使用双指针法，按列相加，分别向左向右遍历，然后每一个位置的雨水=min（左，右）-height，然后累加就可以。

class Solution {
public:int trap(vector<int>& height) {//1.initialvector<int>leftnum(height.size(),0);vector<int>rightnum(height.size(),0);int n=height.size();//2.look forleftnum[0]=height[0];for(int i=1;i<height.size();i++){leftnum[i]=max(leftnum[i-1],height[i]);}rightnum[n-1]=height[n-1];for(int i=n-2;i>=0;i--){rightnum[i]=max(rightnum[i+1],height[i]);}//3.sumint sum=0;for(int i=0;i<height.size();i++){sum+=min(leftnum[i],rightnum[i])-height[i];}return sum;}
};

思路二：单调栈（按行相加）

这个思路比较巧妙，如果成功构造了一个单调栈的话，那么就存在一种情况，b<a且b<c，其中b是栈顶元素，a是当前遍历到的数值，c是栈顶元素的下一个。那么就构成了接雨水的水槽。那么这个可以构成循环一直循环下去，所以我们只需要不断构建这个水槽就可以。

class Solution {
public:int trap(vector<int>& height) {int n=height.size();vector<int>ans(n,0);stack<int>stack;int sum=0;//按行相加for(int i=0;i<n;i++){while(stack.empty()==0&&height[i]>height[stack.top()]){int a=stack.top();stack.pop();if(!stack.empty()){int b=stack.top();int alt=min(height[i],height[b])-height[a];int width=i-b-1;sum+=alt*width;}    }stack.push(i);}return sum;}
};

（5）84. 柱状图中最大的矩形 - 力扣（LeetCode）

解题思路：

1. 首先明确最大矩形怎么找：肯定是通过迭代一步一步更新来的。
2. 那么怎么更新呢，就是通过先找到一个值，这个值右面的所有柱都比他大，也就是说直接用他的高去乘宽就是最大矩形。
3. 如何用到单调栈呢，那就是说单调递减栈，如果当前元素比栈顶元素小则求矩形，否则（大于等于）则入栈。
4. 还要在首尾加两个0，在尾节点加0是因为防止2468这种情况的存在。在头节点加是为了防止8642这种情况出现，无法进行计算，只是一味的弹出。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int>stack;int acre=0;//1.首先处理的时候要首尾加0heights.insert(heights.begin(),0);heights.push_back(0);//2.单调栈的构建for(int i=0;i<heights.size();i++){while(!stack.empty()&&heights[i]<heights[stack.top()]){//单调递减栈int mid=stack.top();stack.pop();if(!stack.empty()){int left=stack.top();int width=i-left-1;int gaodu=heights[mid];acre=max(acre,width*gaodu);}}stack.push(i);}//3.输出return acre;}
};