leetcode84.Largest Rectangle in Histogram

发表于 更新于 分类于 ，

题目要求

1
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.
1
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
1
2
3
4
5
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.

即找到图中可以组合而成的面积最大的矩形。

这里我首先想到的是leetcode 42 Trapping Rain Water，可以参考我的这篇博客。
因为在42题中，如果我找到了当前矩形左右的最近最高矩形即可。而在本题中，同样是需要找到该矩形左右的最高矩形，但不同的是，一旦我在左右搜寻的过程中遇到了一个比当前矩形矮的矩形，遍历即结束。所以两道题目的要求还是存在区别的。

思路一：直观但超时

最直观的思路也就是从当前矩形出发，分别向左向右遍历，一旦遇到一个矩形比当前矩形矮，则该方向的遍历结束。从而我们可以知道该矩形在水平方向上的最大扩展程度。代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
public int largestRectangleArea(int[] heights) {
    int barCount = heights.length;
    
    int max = 0;
    for(int i = 0 ; i<barCount ; i++){
    	int tempHeight = heights[i];
    	int tempWidth = 1;
    	for(int j = i-1 ; j>=0 && heights[j]>=tempHeight ; j--) tempWidth++;
    	for(int j = i+1 ; j<barCount && heights[j]>=tempHeight ; j++) tempWidth++;
    	max = Math.max(max, tempWidth*tempHeight);
    }
    return max;
}

当然，该方法鉴于其需要O(n^2)的时间复杂度，再加上如果出现极端情况即每个矩形都可以水平扩展至n长度，其中n等于数组的长度（例如[1,1,1,1,……,1],n=100000），这样就会带来很多无效的遍历。

思路二：堆栈

如果我们按照顺序从左往右遍历，我们会返现，一旦右边的矩形比左边矮，则左边矩形的向右扩展的程度直接由右边矩形决定。那么我们如何知道左边矩形的左边扩展程度呢。这就需要我们采用栈的模式来记录。一旦新遇到的矩形比栈顶元素矮，我们需要逐个排出栈元素直到栈顶元素大于当前矩形高度。同时我们还需要将当前矩形的数据压入栈中，而当前矩形的左边距则由排出的最后元素的下标决定。也就是说，栈中数据记录了最远左侧下标，而当前的矩形则是最远右侧下标。代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
public int largestRectangleArea(int[] heights) {
    int barCount = heights.length;
    
    int max = 0;
    for(int i = 0 ; i<barCount ; i++){
        int tempHeight = heights[i];
        int tempWidth = 1;
        for(int j = i-1 ; j>=0 && heights[j]>=tempHeight ; j--) tempWidth++;
        for(int j = i+1 ; j<barCount && heights[j]>=tempHeight ; j++) tempWidth++;
        max = Math.max(max, tempWidth*tempHeight);
    }
    return max;
}

思路三：利用已有数据删减遍历

这里我们延续一种的思路，还是采用找到当前矩形的最远左右侧下标，不同的是，我们用两个数据结构int[] lessFromLeft, int[] lessFromRight分别来存储当前矩形的最远左右侧下标。当我们不采用数据结构时，寻找和计算的过程需要O(n^2）的时间复杂度。而通过数据结构，我们可以很大程度上减少遍历次数，对当前矩阵的最左侧下标可以通过lessFromLeft跳跃遍历。也就是说，如果左侧矩形比当前矩形大，则跳到左侧矩形的最左侧矩形继续判断，如果最后调到起点，则结束遍历。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int largestRectangleArea2(int[] heights){
    int barCount = heights.length;
    int max = 0;
    LinkedList<Integer> stack = new LinkedList<Integer>();
    for(int i = 0 ; i<barCount ; i++){
        int tempHeight = heights[i];
        int lastIndex = i;
        while(!stack.isEmpty() && heights[stack.peek()]>tempHeight){
            lastIndex = stack.pop();
            max = Math.max(max, (i-lastIndex)*heights[lastIndex]);
            heights[lastIndex] =tempHeight; 
        }
        stack.push(lastIndex);
    }
    while(!stack.isEmpty()){
        int currentIndex = stack.pop();
        max = Math.max(max, (barCount-currentIndex)*heights[currentIndex]);
    }
    return max;
}