单调栈

单调栈。

判别是否需要使用单调栈，如果需要找到左边或者右边第一个比当前位置的数大或者小，则可以考虑使用单调栈；单调栈的题目如矩形米面积等等

来源739官解评论区

stack存数组的下标。

1	Deque<Integer> stack = new LinkedList<Integer>();

思路是while（栈不空&&当前温度大于栈顶温度），计算ans[]，栈顶出栈。

int length = temperatures.length;
Deque<Integer> stack = new LinkedList<Integer>();
int[] ans = new int[length];
for(int i = 0; i < length; i++){
    int temperature = temperatures[i];
    while(!stack.isEmpty() && temperature > temperatures[stack.peek()]){
        int preIndex = stack.pop();
        ans[preIndex] = i - preIndex;
    }
    stack.push(i);
}

496. 下一个更大元素 I 单调栈+哈希

1	Deque<Integer> stack = new ArrayDeque<>();

ArrayDeque是Deque接口的一个实现，使用了可变数组，容量上没有限制。

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Deque<Integer> stack = new ArrayDeque<>();

for(int i = nums2.length - 1; i >= 0; i--){
    int num = nums2[i];
    while(!stack.isEmpty() && num >= stack.peek()){
        stack.pop();
    }
    map.put(num, stack.isEmpty()? -1: stack.peek());
    stack.push(num);
}

int[] res = new int[nums1.length];
for(int i = 0; i < nums1.length; i++){
    res[i] = map.get(nums1[i]);
}

503. 下一个更大元素 II 单调栈+循环数组

循环数组实际上就是将前n - 1个元素拼接到原数组后面，i % n (pusu)

这题是类似每日温度的题，要用到preIndex，

int n = nums.length;
int[] ret = new int[n];
Arrays.fill(ret, -1);

Deque<Integer> stack = new LinkedList<>(); //存数组下标
for(int i = 0; i < 2 * n - 1; i++){
    int num = nums[i % n];
    while(!stack.isEmpty() && nums[stack.peek()] < num ){
        ret[stack.pop()] = num;
    }
    
    stack.push(i % n); 
}

return ret;

42. 接雨水

有左墙右墙和低洼就可以接雨水，比当前位置高的第一个位置，就是右墙。参考题解评论区，写的非常清楚。

public int trap(int[] height) {
    if(height == null || height.length <= 2){
        return 0;
    }

    int n = height.length;
    int water = 0;
    Deque<Integer> stack = new ArrayDeque<>();//存下标

    for(int right = 0; right < n; right++){
        while(!stack.isEmpty() && height[right] > height[stack.peek()]){
            int bottom = stack.pop();//底
            if(stack.isEmpty()){//无左墙，没法接雨水
                break;
            }

            int left = stack.peek();
            water += (right - left - 1) * (Math.min(height[left], height[right]) - height[bottom]);
        }

        stack.push(right);
    }
    return water;

}

84. 柱状图中最大的矩形

理解题意，可以枚举高度和枚举宽度。枚举高度时，是当前位置i向左向右延伸，找到第一个低于height[i]的位置，right[i]和left[i]，两者之间的长度就是矩形的宽。因为是找左右第一个比当前位置小的数，可以用到单调栈。优化之后可以一次遍历找到左右的位置。

int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];//存位置下标
Arrays.fill(right, n);//初始化

Deque<Integer> stack = new ArrayDeque<>();
for(int i = 0;i < n; i++){
    while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
        right[stack.peek()] = i;
        stack.pop();
    }
    left[i] = (stack.isEmpty()? -1 : stack.peek());
    stack.push(i);
}

int ans = 0;
for(int i = 0; i < n; i++){
    ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}