Day51：503.下一个更大元素II、42. 接雨水

503.下一个更大元素II

题目链接

思路

这道题和下一个更大元素 I的不同之处在于这个查找是循环的。
循环直接可以用查找两次来解决，所以题目步骤唯一不同的就是循环的终止位置。

for(int i=1;i<nums.size()*2;i++){
	while(!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
		result[st.top()] = nums[i % nums.size()];
		st.pop();
	}
	st.push(i%nums.size());
}

代码实现

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        vector<int> result(nums.size(),-1);
        for(int i=1;i<nums.size()*2;i++){
            while(!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i%nums.size());
        }
        return result;
    }
};

42. 接雨水

题目链接

思路

这道题直接变成困难题，愿意就是前面的题目都是找一边的最大值，而这道题是找两边的最大值。其实意识到这一点，这道题也没那么难了。
已经知道单调栈储存的元素是从栈头到栈底单调递增的元素。在遍历元素Height[i]和st.top()相比较时，会出现三种情况：

1. Height[i] 大于 Height[st.top()]
2. Height[i] 等于 Height[st.top()]
3. Height[i] 小于 Height[st.top()]

情况2和情况3和之前操作一样，先把元素放入栈内保存着，遍历寻找下一个比它大的元素。
而情况1表明找到了st.top()前比它大的元素位置，而st.top()后比他大的元素位置就是它在栈内位置的下方元素，那么这道题就迎刃而解了，困难题也没有那么“困难”。

代码实现

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