Largest Rectangle in Histogram

Leave a comment

August 25, 2016 by oneOokay

类似:trapping-rain-water

以及相关应用: Maximal Rectangle

基本思想:对于一个heights[i],找出i向左的第一个小于它的数(heights[m])和i向右的第一个小于它的数(heights[n]),那么包含heights[i]这个点的最大的area是,height[m]之后一个数到heights[n]之前一个数距离乘以heights[i]

需要了解一个叫做单调栈的概念:一个stack,里面的元素单调递增或者单调递减。

e.g: 构建一个单调递增栈:2,1,5,6,2,3

  • 2=> 栈为空,push:2。    栈:[2
  • 1=> 栈不为空,栈内peek=2,2 > 1,POP:2,push:1 。栈:[1  (area = 2 * 1 = 2)
    • POP出2之后,对于2这个数字:往左第一个比它小的数字不存在(为边界了因为stack为空了,接下来会讲push进-1来帮助计算长度);往右第一个比他小的数字为1.
  • 5=>栈不为空,栈内peek=1,1<5, push 5。 栈:[1,5
  • 6=>栈不为空,栈内peek=5, 5<6, push 6。栈:[1,5,6
  • 2=>栈不为空,栈内peek=6,6>2, POP 6。栈:[1,5
    • 此时我们可以得知,6这个数往左,第一个比它小的数为5(peek);6这个数往右,第一个比它小的数为2。所以area:6 * ((4-1) – (2 + 1) + 1) = 6
      • (4 – 1): 2 的index – 1:2为右边第一个小的数
      • (2 + 1): 5 的index + 1: 5 为左边第一个小的数
      • 距离:index1 – index2 + 1
      • 以此类推。
  • 2的处理还没有结束,栈不为空,栈内peek= 5 (6已经被pop出去了), 5 > 2, POP 5. 栈[1
  • 5往左第一个小的数为1(index =1),5往右的第一个小的数为2(index = 4). area = 5 * ((4-1) – (1+1)+1) = 10.
  • 2的处理继续,栈不为空,栈内peek=1,1<2,push2. 栈 [1,2
  • 3=>栈不为空,栈内peek=2, 2<3, push 3. 栈[1,2,3
  • 到此loop完了所有数字,处理完毕。那如何把这123给pop出来呢,我们继续push进一个-1 (index = 6)
  • -1=> 栈不为空,栈内peek=3, 3>-1, POP 3. area = 3 * ((6-1) – (4+1) + 1 )= 3
  • 栈不为空,栈内peek=2, 2>-1, POP2. area = 2 * (6 – 1 -1) = 8 (简化了)
  • 栈不为空,栈内peek=1, 1>-1, POP1. area = 1 * 6 = 6. 
  • 当pop之后栈为空时,width = 当前处理值的index
  • 最终的-1不需要pop。

所以在处理一个heights[i]的array的时候技巧:

  • 把height的index push到stack里面.
  • 最后当i==heights.length的时候,push -1入栈来清空栈
  • index (i , j)之间的距离的计算方法是: (j – 1) – (i + 1) + 1 = j – i -1
  • 当pop出一个元素使得栈为空时,stack.peek() will throw exception.这时候的width=待push入栈的(index – 1) – 0 + 1 = index
  • 时间复杂度为O(n) 不是O(n^2):因为for-loop为n,如果while要达到O(n)的话,for-loop中要已经push过n个数了,所以不可能是O(n^2)
  • 或者:n个数,每个数进出stack只一次,那么它的时间复杂度就是n*O(1) = O(n)
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
Stack stack = new Stack<>();
int max = 0;
for (int i = 0; i <= height.length; i ++) { 
//=的原因是在处理完所有的数字之后(i==height.length)时,push -1 进入stack来清空栈
int current = (i == height.length)? -1 : height[i]; //引入-1
while(!stack.isEmpty() && current <= height[stack.peek()])
{
int h = height[stack.pop()];
int w = stack.isEmpty()? i : (i - 1) - (stack.peek() + 1) + 1; 
//当栈为空时,width = i
max = Math.max(max, h * w);
}
stack.push(i);
}
return max;
}

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.


这题有一个DP的解法…好复杂看不懂…但是可以用Largest Rectangle in Histogram的方法来做的.

  • 从第一行开始往下扫,生成一个heights[] array,对每一行的heights array用Largest Rectangle in Histogram的方法来求max area.最终取其最大就可以了.
  • 生成heights array的时候,如果当前行为0,那么height reset to 0, 否则的话累加1.
public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) 
            return 0;
        int[] heights = new int[matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix.length; i ++){
            heights = getHeights(matrix, i, heights);
            max = Math.max(max, getMaxArea(heights));
        }
        return max;
    }
    
    private int[] getHeights(char[][] matrix, int row, int[] heights){
        for (int i = 0; i < heights.length; i ++){
            if (matrix[row][i] == '0') heights[i] = 0;
            else heights[i] ++;
        }
        return heights;
    }
    
    private int getMaxArea(int[] heights){
        Stack<Integer> stack = new Stack<>();
        int area = 0;
        for (int i = 0; i <= heights.length; i ++){
            int cur = i == heights.length ? -1 : heights[i];
            while (!stack.isEmpty() && cur <= heights[stack.peek()]){
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                area = Math.max(area, h * w);
            }
            stack.push(i);
        }
        return area;
    }
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

%d bloggers like this: