84. Largest Rectangle in Histogr

public int largestRectangleArea2(int[] heights) {
    if (heights == null) {
        return 0;
    }
    ArrayList<Integer> list = wrapArray(heights);
    
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    
    for (int i = 1; i < list.size(); i++) {
        while (list.get(stack.peek()) > list.get(i)) {
            int index = stack.pop();
            int currArea = (i - stack.peek() - 1) * list.get(index);
            maxArea = Math.max(maxArea, currArea);
        }
        stack.push(i);
    }
    
    return maxArea;
}

// wrap array with beginning and ending height 0
private ArrayList<Integer> wrapArray(int[] heights) {
    ArrayList<Integer> list = new ArrayList<>(heights.length + 2);
    list.add(0);
    for (int h: heights) {
        list.add(h);
    }
    list.add(0);
    return list;
}

这种 Wrapper 方式比较好理解题解思路，以及处理 Corner case。下面的题解思路同上面一致。

public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    
    for (int i = 1; i < heights.length; i++) {
        while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
            int index = stack.pop();
            int leftBound = stack.isEmpty() ? -1 : stack.peek();
            int currArea = (i - leftBound - 1) * heights[index];
            maxArea = Math.max(maxArea, currArea);
        }
        stack.push(i);
    }
    
    // int rightBound = stack.peek() + 1;
    int rightBound = heights.length;    // the top element must be the last index of the array
    while (!stack.isEmpty()) {
        int index = stack.pop();
        int leftBound = stack.isEmpty() ? -1 : stack.peek();
        int currArea = (rightBound - leftBound - 1) * heights[index];
        maxArea = Math.max(maxArea, currArea);
    }
    
    return maxArea;
}

另一种类似写法：

public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    
    for (int i = 0; i <= heights.length; i++) {
        int h = (i == heights.length) ? 0 : heights[i];
        while (!stack.isEmpty() && heights[stack.peek()] > h) {
            int index = stack.pop();
            int leftBound = stack.isEmpty() ? -1 : stack.peek();
            int currArea = (i - leftBound - 1) * heights[index];
            maxArea = Math.max(maxArea, currArea);
        }
        stack.push(i);
    }
    
    return maxArea;
}