单调栈的作用

就是用一个栈来记录我们遍历过的元素

单调栈里存放元素下标i就可以了，如果要使用对应元素，直接T[i]就可以获取到

从栈头到栈尾-递增的话-栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i

题目

LeetCode:739.每日温度

解法

将下标存放进单调栈中

当前遍历的元素和栈顶元素进行比较T[i]和T[st.pop()]

T[i]==T[st.pop()] 入栈

T[i]>T[st.pop()] 记录结果

T[i]

class Solution {
public:vector dailyTemperatures(vector& temperatures) {stack st;vector reulst(temperatures.size(),0);st.push(0);//放入第一个元素for(int i=1;itemperatures[st.top()]){reulst[st.top()]=i-st.top();st.pop();}st.push(i);}}return reulst;}
};

LeetCode:496.下一个更大

解法

class Solution {
public:vector nextGreaterElement(vector& nums1, vector& nums2) {vector result(nums1.size(),-1); //结果数组的长度与1相等stack st;if(nums1.size()==0) return result;unordered_map umap;//对数组1进行处理 建立哈希表for(int i=0;inums2[st.top()]){//判断元素是否出现过if(umap.count(nums2[st.top()])>0){int index=umap[nums2[st.top()]];result[index]=nums2[i];}st.pop();}st.push(i);}}return result;}
};

LeetCode:503.下一个更大元素II

用取模的过程模拟成环的遍历

for(i=0;i

i%nums.size()

}

class Solution {
public:vector nextGreaterElements(vector& nums) {vector result(nums.size(),-1);stack st;st.push(0);//放入第一个元素for(int i=1;inums[st.top()]){result[st.top()]=nums[i%nums.size()];st.pop();}st.push(i%nums.size());}}return result;}
};

LeetCode:42.接雨水

class Solution {
public:int trap(vector& height) {stack st;st.push(0);int sum=0;//从1开始遍历所有柱子for(int i=1;iheight[st.top()]){int mid=height[st.top()];st.pop();if(!st.empty()){int h=min(height[i],height[st.top()])-mid;int w=i-st.top()-1;sum+=h*w;}}st.push(i);}}return sum;}
};

LeetCode:84.柱状图中最大的矩形

class Solution {
public:int largestRectangleArea(vector& heights) {int result=0;stack st;heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.push(0);for(int i=1;i=heights[st.top()]){st.push(i);}//条件2 小于的情况else{while(!st.empty()&&heights[i]

感觉是最难理解的一部分了&完结撒花