单调栈

例题1：leetcode84：柱状图中最大矩形

// 单调栈，栈中存放的是坐标
public int largestRectangleArea(int[] heights) {
    int n = heights.length, max = 0;
    int[] left = new int[n];
    int[] right = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for(int i = 0; i < n; i++) {
        while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
            stack.pop();
        }
        left[i] = stack.isEmpty() == true ? -1 : stack.peek();
        stack.push(i);
    }
    stack = new ArrayDeque<>();
    for(int i = n - 1; i >= 0; i--) {
        while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
            stack.pop();
        }
        right[i] = stack.isEmpty() == true ? n : stack.peek();
        stack.push(i);
    }
    for(int i = 0; i < n; i++) {
        max = Math.max(max, (right[i] - left[i] - 1) * heights[i]);
    }
    return max;
}