503.下一个更大元素||

链接：LeetCode503下一个更大元素||

class Solution {
public:typedef pair<int,int> pa;vector<int> nextGreaterElements(vector<int>& nums) {int len = nums.size();for(int i=0;i<len;++i) nums.push_back(nums[i]);stack<pa> st;st.push(pa{nums[0],0});vector<int> ans(len,-1);for(int i=1;i<nums.size();++i){while(!st.empty()&&nums[i]>st.top().first){if(st.top().second<len)ans[st.top().second] = nums[i];st.pop();}st.push(pa{nums[i],i});}return ans;}
};

42.接雨水

链接：LeetCode42.接雨水

暴力解法(双指针)

按照列计算

按照列计算，宽度是1，此时把每一列的高度求出来就可以了。
每一列雨水的高度取决于该列左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。

class Solution {
public:int trap(vector<int>& height) {int ans = 0;for(int i=0;i<height.size();++i){int lheight = height[i];//左边柱子的最高高度int rheight = height[i];//右边柱子的最高高度if(i==0 || i==height.size()-1) continue;//第一根柱子和最后一根柱子不接雨水for(int j=i+1;j<height.size();++j) if(height[j]>rheight) rheight=height[j];for(int j=i-1;j>=0;--j) if(height[j]>lheight) lheight = height[j];int h = (lheight<rheight?lheight:rheight) - height[i];if(h>0) ans += h;}return ans;}
};

双指针优化

把每一个位置的左边最高高度记录在一个数组上maxLeft ,右边最高高度记录在一个数组上maxright.这样就避免了重复计算

class Solution {
public:int trap(vector<int>& height) {vector<int> maxlheight(height.size(),0);vector<int> maxrheight(height.size(),0);maxlheight[0] = height[0];for(int i=1;i<height.size();++i){maxlheight[i] = max(height[i],maxlheight[i-1]);}maxrheight[height.size()-1] = height[height.size()-1];for(int i=height.size()-2;i>=0;--i){maxrheight[i]=max(maxrheight[i+1],height[i]);}int ans = 0;for(int i=0;i<height.size();++i){if(i==0 || i==height.size()-1) continue;//第一根柱子和最后一根柱子不接雨水int h = min(maxlheight[i],maxrheight[i]) - height[i];if(h>0) ans += h;}return ans;}
};

单调栈

寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时就要使用单调栈。

class Solution {
public:typedef pair<int,int>pa;int trap(vector<int>& height) {if(height.size()<3) return 0;int ans=0;stack<pa> st;for(int i=0;i<height.size();++i){while(!st.empty()&&height[i]>st.top().first){if(st.size()>=2){int mid = st.top().first;st.pop();// while(!st.empty()&&st.top().first<=mid) st.pop();// if(st.empty()) break;int le = st.top().first;int width = i-st.top().second-1;int len = (height[i]<le?height[i]:le) - mid;ans += width*len;//cout<<width<<"  "<<len<<"  "<<ans<<"  ";}else st.pop();}st.push(pa{height[i],i});}return ans;}
};