73.Largest Rectangle in Histogram（最大矩形）

Level：

  Hard

题目描述：

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.

Example:

Input: [2,1,5,6,2,3]
Output: 10

思路分析：

  将每一个height[ i],都作为一个矩形高度的最低点，向两边扩展，找到左右都比它小，停止，计算面积，最后在这些求出的面积中找出最大值。时间复杂度为O(n)。

代码：

public class Solution{
    public int largestRectangleArea(int []heights){
        if(heights==null||heights.length==0)
            return 0;
        Stack<Integer>s=new Stack<>(); //存放的是数组的下标
        int maxarea=0;
        for(int i=0;i<=heights;i++){
            int h=(i==heights.length)?0:height[i]; //最后添加一个零是为了让栈中最后一个元素能弹出
            if(s.isEmpty()||h>=heights[s.peek()]){ //能保证height[i]左边都比其小
                s.push(i);
                
            }else{
                int tp=s.pop();
                maxarea=Math.max(maxarea,heights[tp]*(s.isEmpty()?i:i-s.peek()-1));
                i--;
            }
        }
        return maxarea;
    }
}