84. 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.

histogram_area

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.首先什么时候计算长方形面积?
2.如何确定长方形的长,宽跟高?
我们这样来想,如果每次找到的元素都比之前元素的值要大,就说明之前的长方形包含在新加入的元素组成的长方形里面;原来的长方形被extend了,而这个过程是个单调递增过程。 如果找到元素比之前元素小,那么说明之前的长方形不能extend了(这时候我们也找到了右边界),也就需要计算之前长方形的面积;如果确定左边界呢? 我们可以用stack把之前的点的坐标都保存起来,而放入stack中的条件就是当前元素的值要大于栈顶元素的值,这样才能保证你的长方形是一直extend的。 当当前元素的值比stack栈顶元素值小的时候,确定右边界为当前元素坐标, 而左边界, 跟长方形的高则需要不停的pop stack中的元素来获得; 计算长方形面积are = h*(right – left),并跟一个全局变量max进行比较。 注意当遍历到最后一个元素的时候,右边界也就是数组的长度, 我们要不停的pop出stack中的元素获得左边界并计算, 当stack为空的时候,不要忘记左边界可以获得0, 计算整个数组长度为宽构成的长方形面积。

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) 
            return 0;
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= heights.length; i++) {
            int curVal = i == heights.length ? 0 : heights[i];
            while(!stack.isEmpty() && curVal <= heights[stack.peek()]) { // 当前index元素的height小于等于栈顶元素的height, 即找到了右边界, 需要连续pop stack来获得左边界并进行计算.
                int h = heights[stack.pop()];
                int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                int right = i;
                int area = h * (right - left);
                max = Math.max(area, max);
            }
            stack.push(i); 
        }
        return max;    
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s