代码随想录算法训练营刷题复习4 ：单调栈

单调栈

单调栈
如果题目出现典型的
【左小 中大(栈中左侧元素都比此值小) || 右小】（寻找右侧第一个比此值小的元素）
【左大 中小(栈中左侧元素都比此值大) || 右大】（寻找右侧第一个比此值大的元素）
数据关系的话，可以考虑使用单调栈解决问题

1. 739. 每日温度

2. 496. 下一个更大元素 I

3. 503. 下一个更大元素 II

4. 42. 接雨水

5. 84. 柱状图中最大的矩形这个题忽略了对数组头和尾添加0以方便对头和尾元素的处理

4、5这两个题可以总结为单调栈中求面积问题：找所求区域的高和宽

739. 每日温度

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {if(temperatures.size()<=1)return vector<int>(0);//需要用到栈和数组stack<int> st;vector<int> result(temperatures.size(),0);// 初始化把第一个元素的下标入栈st.push(0);for(int i=1;i<temperatures.size();i++) {//栈顶的元素值与当前遍历的值作比较if(temperatures[i] <= temperatures[st.top()]) {st.push(i);}else {//遇到第一个比当前值大的值时，用while循环来循环处理while(!st.empty() && temperatures[i] > temperatures[st.top()]){result[st.top()] = i-st.top();st.pop();}//处理结束说明栈中已经没有比当前遍历元素还小的值了，就把i入栈st.push(i);}}return result;}
};

496. 下一个更大元素 I

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> umap;//想要存 <键值,下标>这个关系// 下文中需要判断nums2中的值是否在nums1中出现，下标零出现误判，故使用i+1for(int i=0;i<nums1.size();i++) {umap[nums1[i]]=i+1;}if(nums1.size()==0 || nums2.size()==0)return vector<int>(nums1.size(),-1);stack<int> st;vector<int> ans(nums1.size(),-1);//这个数据没必要存了其实// vector<int> temp(nums2.size(),-1);st.push(0);for(int i=1;i<nums2.size();i++) {if(nums2[i] <= nums2[st.top()]) {st.push(i);}else {while(!st.empty() && nums2[i] > nums2[st.top()]) {// temp[st.top()] = nums2[i];if(umap[nums2[st.top()]]!=0) {ans[umap[nums2[st.top()]] -1] = nums2[i];}st.pop();}st.push(i);}}return ans;}
};

503. 下一个更大元素 II

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {//通过复制数组，将循环问题转化为不循环问题vector<int> nums1(nums.begin(),nums.end());// insert函数参数需要，插入位置，以及插入的元素范围nums.insert(nums.end(),nums1.begin(),nums1.end());stack<int> st;vector<int> res(nums.size(),-1);st.push(0);for(int i=1;i<nums.size();i++) {if(nums[i]<=nums[st.top()]) {st.push(i);}else {while(!st.empty() && nums[i]>nums[st.top()] ) {res[st.top()] = nums[i];st.pop();}st.push(i);}}//恢复原先数组大小res.resize(nums.size()/2);return res;}
};

42. 接雨水

class Solution {
public:int trap(vector<int>& height) {if(height.size()<=2)return 0;stack<int> st;// vector<int> res(height.size(),0);st.push(0);int result = 0;for(int i=1;i<height.size();i++) {if(height[i] < height[st.top()]) {st.push(i);}else if(height[i] == height[st.top()]) {st.pop();st.push(i);}else {while(!st.empty() && height[i] > height[st.top()]) {int mid = st.top();st.pop();if(!st.empty()){int left = st.top();int w = i-left-1;int h = min(height[i],height[st.top()])-height[mid];result+=h*w;}}st.push(i);}}return result;}
};

84. 柱状图中最大的矩形

class Solution {
public:int largestRectangleArea(vector<int>& heights) {if(heights.size()==0)return 0;if(heights.size()==1)return heights[0];//这里对原始数组的头尾添加0值忘记考虑了heights.insert(heights.begin(),0);heights.push_back(0);stack<int> st;int res=0;st.push(0);for(int i=1;i<heights.size();i++) {if(heights[i]>heights[st.top()])st.push(i);else if(heights[i] == heights[st.top()]) {st.pop();st.push(i);}else {while(!st.empty() && heights[i]< heights[st.top()]) {int mid = st.top();st.pop();if(!st.empty()) {int left = st.top();int w = i-left-1;res = max(res,w*heights[mid]);}}st.push(i);}}return res;}
};