题目：

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
     
       stack = new Stack
      
       ();        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));    }}