leetcode解题: Largest Rectangle in Histogram (84)

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

解法1：Stack O(N)

这题的思路比较巧妙。一般的思路计算面积，办法是先找出左右的边界，然后找出高度。那么这种算法的复杂度是O(N^3)的。
如果我们换一个思路，枚举高度而不是枚举边界。那么对于任意一个高度的bar，我们只需要找出来他左面第一个比它矮的和右边第一个比它矮的bar就能算出来对应的使用这个bar作为最高高度的面积了。
那么这里需要记录左面的已经遍历过的高度。如果说我们维护一个递增的stack，每一个栈顶元素他对应的左面的比他小的bar的位置就确定了。
如果碰到右面比他矮的bar，那么我们就可以计算出当前栈顶的bar对应的面积。
stack中存上index而不是高度方便计算面积
并且要注意计算到最后一个bar之后要清理stack中还存在的bar
Java

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<Integer>();
        int max = Integer.MIN_VALUE;

        stack.push(0);

        for (int i = 1; i < heights.length; ++i) {
            int current = heights[i];
            while (!stack.isEmpty() && current < heights[stack.peek()]) {
                int bar = heights[stack.pop()];
                int left = stack.isEmpty()? -1 : stack.peek();
                max = Math.max(bar * (i - left - 1), max);
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int bar = heights[stack.pop()];
            while (!stack.isEmpty() && heights[stack.peek()] == bar) {
                stack.pop();
            }
            int left = stack.isEmpty() ? -1 : stack.peek();
            max = Math.max(max, bar * (heights.length - left - 1));
        }

        return max;
    }
}

另一种写法较为简单。诀窍是在数组的最后放一个0，这样可以保证清空stack中的值。

public class Solution {
    public int largestRectangleArea(int[] heights) {

        if (heights == null || heights.length == 0) {
            return 0;
        }

        int res = 0;
        Stack<Integer> stack = new Stack<Integer>();

        int[] h = Arrays.copyOf(heights, heights.length + 1); // padding zero at the end

        for (int i = 0; i < h.length; ++i) {
            int bar = h[i];
            while (!stack.empty() && bar < h[stack.peek()]) {
                int last = h[stack.pop()];
                // calculate the width
                int width = stack.empty() ? i : i - stack.peek() - 1;
                res = Math.max(res, width * last);
            }
            stack.push(i);
        }

        return res;

    }
}