单调栈（下一个更大元素+滴雨水

下一个更大元素（成环

用取模的方式来模拟转圈的过程

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int len=nums.length;
        int[] res=new int[len];
        Deque<Integer> stack=new LinkedList<>();
        Arrays.fill(res,-1);
        for(int i=0;i<2*len;i++){
            while(!stack.isEmpty()&&nums[i%len]>nums[stack.peek()]){
                int x=stack.pop();
                res[x]=nums[i%len];
            }
            stack.push(i%len);
        }
        return res;
    }
}

接雨水（用双指针或者单调栈

双指针比较简单，要先初始化左边界和右边界。+动态规划

找出 当前柱子的左边最大值和右边最大值，取最小的再与当前元素的差值即可。

class Solution {
    public int trap(int[] height) {
        int len=height.length;
        int[] maxLeft=new int[len];//记录当前元素左边最大元素
        int[] maxRight=new int[len];
        int sum=0;
        maxLeft[0]=height[0];
        maxRight[len-1]=height[len-1];//初始化
        for(int i=1;i<len;i++){
            maxLeft[i]=Math.max(maxLeft[i-1],height[i]);
        }
        for(int i=len-2;i>=0;i--){
            maxRight[i]=Math.max(maxRight[i+1],height[i]);
        }
        for(int i=0;i<len;i++){
            sum+=Math.min(maxLeft[i],maxRight[i])-height[i];
        }
        return sum;
    }
}

单调栈

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack=new LinkedList<>();
        int sum=0;
        int len=height.length;
        for(int i=0;i<len;i++){
            while(!stack.isEmpty()&&height[i]>height[stack.peek()]){
                int mid=height[stack.pop()];
                if(!stack.isEmpty()){
                     int left=stack.peek();
                     int area=(Math.min(height[i],height[left])-mid)*(i-left-1);
                     sum+=area;
                }
            }
            stack.push(i);
        }
        return sum;
    }
}