503.下一个更大元素II
两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以
vector<int>nextGreaterElements(vector<int>&nums){// 拼接一个新的numsvector<int>nums1(nums.begin(),nums.end());nums.insert(nums.end(),nums1.begin(),nums1.end());// 用新的nums大小来初始化resultvector<int>result(nums.size(),-1);if(nums.size()==0)returnresult;// 开始单调栈stack<int>st;st.push(0);for(inti=1;i<nums.size();i++){if(nums[i]<nums[st.top()])st.push(i);elseif(nums[i]==nums[st.top()])st.push(i);else{while(!st.empty()&&nums[i]>nums[st.top()]){result[st.top()]=nums[i];st.pop();}st.push(i);}}// 最后再把结果集即result数组resize到原数组大小result.resize(nums.size()/2);returnresult;}
42. 接雨水
三种情况
情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
if (height[i] < height[st.top()]) st.push(i);
情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
if (height[i] == height[st.top()]) { // 例如 5 5 1 7 这种情况
st.pop();
st.push(i);
}
情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]
int h = min(height[st.top()], height[i]) - height[mid];
inttrap(vector<int>&height){stack<int>st;st.push(0);intsum=0;for(inti=1;i<height.size();i++){while(!st.empty()&&height[i]>height[st.top()]){intmid=st.top();st.pop();if(!st.empty()){inth=min(height[st.top()],height[i])-height[mid];intw=i-st.top()-1;sum+=h*w;}}st.push(i);}returnsum;}
