LeetCode - Largest Rectangle in Histogram

題目：

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 height = [2,1,5,6,2,3],
return 10.

思路：

1）對每個直方維護它能拓展到左右兩邊最遠的邊界。

package area;

public class LargestRectangleInHistogram {

    public int largestRectangleArea(int[] height) {
        int n = height.length;
        int max = 0;
        int[] left = new int[n];
        int[] right = new int[n];
        for (int pos = 0; pos < n; ++pos) {
            left[pos] = right[pos] = pos;
            int i = pos - 1;
            for (; i >= 0; --i) {
                if (height[i] < height[pos]) {
                    left[pos] = i + 1;
                    break;
                }
            }
            if (i == -1) left[pos] = 0;
            
            for (i = pos + 1; i < n; ++i) {
                if (height[i] < height[pos]) {
                    right[pos] = i - 1;
                    break;
                }
            }
            if (i == n) right[pos] = n - 1;
            int area = height[pos] * (right[pos] - left[pos] + 1);
            if (area > max)
                max = area;
        }

        return max;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] height = { 1,1,1,1 };
        LargestRectangleInHistogram l = new LargestRectangleInHistogram();
        System.out.println(l.largestRectangleArea(height));
    }

}

2）維護一個棧，對比當前元素，如果大於當前元素，則pop，否則push當前元素的index

package area;

import java.util.Stack;

public class LargestRectangleInHistogram {

    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        int n = height.length;
        int[] newHeight = new int[n + 1];
        for (int i = 0; i < n; ++i) newHeight[i] = height[i];
        newHeight[n] = 0;
        int i = 0;
        while (i < n + 1) {
            if (stack.isEmpty() || newHeight[stack.peek()] <= newHeight[i]) {
                stack.push(i++);
            } else {
                int index = stack.pop();
                int area = (stack.isEmpty() ? i : (i - stack.peek() - 1)) * newHeight[index];
                max = (max < area ? area : max);
            }
        }
        
        return max;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] height = { 1,1 };
        LargestRectangleInHistogram l = new LargestRectangleInHistogram();
        System.out.println(l.largestRectangleArea(height));
    }

}