即速应用小程序官网_ui交互设计用什么软件_合肥seo整站优化网站_企业培训课程种类

用数组模拟栈，tt指向栈顶。
从尾部开始遍历，如果当前温度大于等于栈顶的温度就把栈顶温度删了，因为再往前的元素比它大的最近的都不可能是这个。
如果栈有元素，取出下标与当前下标做差
最后把该下标放入栈中

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n=temperatures.size();vector<int> answer(n,0);int stk[100005],tt=0;for(int i=n-1;i>=0;i--){while(tt&&temperatures[i]>=temperatures[stk[tt]])tt--;if(tt)answer[i]=stk[tt]-i;stk[++tt]=i;}return answer;}
};

对于这题我们先遍历nums2数组，把每一个元素最右边的更大值存进哈希表里，再遍历一遍nums1数组即可。
stk依旧用数组模拟栈，然后遍历一遍nums2，栈中存目前为止的较大元素，如果栈不为空存入哈希表里，否则哈希表里存-1，把当前元素加入栈中。
遍历一遍nums1，把哈希表里对应的值取出来放入答案中。

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int l1=nums1.size(),l2=nums2.size();unordered_map<int,int> m;vector<int>ant;int stk[1005],tt=0;for(int i=l2-1;i>=0;i--){while(tt&&nums2[i]>=stk[tt])tt--;if(tt)m[nums2[i]]=stk[tt];else m[nums2[i]]=-1;stk[++tt]=nums2[i];}for(int i:nums1)ant.push_back(m[i]);return ant;}
};

这道题先遍历一遍数组，初始化一下单调栈，再从尾部往前遍历一遍，更新答案，栈不为空就放入栈中

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int l=nums.size();vector<int>ant(l);int stk[10005],tt=0;for(int i=l-1;i>=0;i--){while(tt&&nums[i]>=stk[tt])tt--;stk[++tt]=nums[i];}for(int i=l-1;i>=0;i--){while(tt&&nums[i]>=stk[tt])tt--;if(tt)ant[i]=stk[tt];else ant[i]=-1;stk[++tt]=nums[i];}return ant;}
};

这里采用两次遍历，找每个位置左右两边的最大高度，注意不是最近的比它大的高度，然后算一下两边位置的较小值，与height[i]做差加到answer中

class Solution {
public:int trap(vector<int>& height) {int answer=0;int n=height.size();vector<int> left(n+5,-1),right(n+5,-1);vector<int> stk(n+5);int tt=0;for(int i=0;i<n;i++){while(tt&&height[i]>=stk[tt])tt--;if(tt)left[i]=stk[tt];else stk[++tt]=height[i];}tt=0;for(int i=n-1;i>=0;i--){while(tt&&height[i]>=stk[tt])tt--;if(tt)right[i]=stk[tt];else stk[++tt]=height[i];}for(int i=1;i<=n-2;i++){int t=min(left[i],right[i]);if(t>0)answer+=t-height[i];}return answer;}
};

这道题也是用两边单调栈，但跟上一题有略微的小调整，栈里存下标，并且处理方式也不一样，这里是较小栈。
最后遍历算面积取最大值即可

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n=heights.size();
vector<int> left(n),right(n);
int ant=0;   int stk[100005],tt=0;for(int i=0;i<n;i++){while(tt&&heights[i]<=heights[stk[tt]])tt--;if(tt)left[i]=stk[tt];else left[i]=-1;stk[++tt]=i;}tt=0;for(int i=n-1;i>=0;i--){while(tt&&heights[i]<=heights[stk[tt]])tt--;if(tt)right[i]=stk[tt];else right[i]=n;stk[++tt]=i;}for(int i=0;i<n;i++){ant=max(ant,(right[i]-left[i]-1)*heights[i]);}return ant;}
};