/**
1. 把问题具体化,  能够勾勒出来的矩形的最大面积 -> MAX(每个矩形能向左向右扩展出的面积)
2. 矩形的扩展面积 = 矩形高度 * (右扩展边界 - 左扩展边界)
3. 左扩展边界 -> 对应矩形左边第一个比他矮的位置 -> 维护一个递增的单调栈, 当元素要入栈时, 栈顶元素内侧即为扩展边界, 空栈边界为最开始的元素
4. 右边界同理
*/

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int[] left =  leftBound(heights, stack);
        int[] right = rightBound(heights, stack);
        int result = 0;
        for (int i = 0 ; i < heights.length;  i++)  
            result = Math.max(result, heights[i] * (right[i] - left[i] + 1));

        return result;
    }

    public int[] rightBound(int[] h, Stack<Integer> stack){
        int[] bound = new int[h.length];
        stack.clear();
        for (int i = h.length - 1 ; i >= 0 ; i--){
            while(!stack.isEmpty() && h[stack.peek()] >= h[i]) stack.pop();
            bound[i] = stack.isEmpty() ? h.length - 1 : stack.peek() - 1; 
            stack.push(i);
        }
        return bound;
    }

    public int[] leftBound(int[] h, Stack<Integer> stack){
        int[] bound = new int[h.length];
        stack.clear();
        for (int i = 0 ; i < h.length ; i++){
            while(!stack.isEmpty() && h[stack.peek()] >= h[i]) stack.pop();
            bound[i] = stack.isEmpty() ? 0 : stack.peek() + 1; 
            stack.push(i);
        }
        return bound;
    }
}