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;
}

Maximal Rectangle

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.


  • 一行一行的从上往下扫描,维护一个heights int array表示以从上到当前点为终点的1的长度为height. 当对当前行从左到右扫描的时候,对每一个height进行判断.
  • 维护一个什么样的栈?递增栈(可以存在相等的元素:如: 1 2 2 3)
    • 递增栈的特点在于,已经在栈里面的每一个元素,它栈之下的一个元素是array中第一个小于它的元素.
  • 把什么放到stack里?把height的index放到stack里.这样我们就可以通过index来求长方形的width了. height可以直接通过index到heights array里面取.
  • 什么时候进栈?遍历每一个height array元素的时候.
    1. 当栈为空时候加入当前index
    2. 当栈顶peek的index对应的height小于等于当前height的时候,把当前index push进栈.
    3. 当不满足条件1和2对栈pop完之后把当前的j放到栈里面.因为已经pop掉了比它大的数字,继续加入它来维持一个递增栈.
  • 什么时候出栈?当当前height小于栈顶peek index对应的height的时候,开始pop.
    • 那么对于当前栈顶的这个index在的height来说,就出现了往左第一个比它小的height(栈里头底下的那个数)和往右第一个比它小的数(暂时还未入栈).
  • 什么时候计算area?就在pop的时候. pop的时候,可以求的以被pop出来的这个height值为高度的rectangle的area. (由pop出的index找到heights array里面的height; 由它之前的那个index得出rectangle的width的左边的值, 由当前的index j为rectangle的width的右边的值即可求出width) 所以area = height[index] * j – pre – 1. 同时更新maxArea的值.
  • trick: 这里的heights array的长度为matrix[0].length + 1: 比matrix自身的n要多一个.在heights的最后一个放入一个值,这个值会被用来pop out在stack里面的所有元素.
  • 因为heights length比当前的n要多1,所以内层对单行进行循环的最后stack里面是永远会存在一个元素的. 所以在开始对下一层处理的时候, stack要重新initiate.
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int m = matrix.length, n = matrix[0].length, max = 0, h = 0, pre = 0;
        int[] heights = new int[n + 1];
        heights[n] = -1;
        Stack s = new Stack<>();
        for(int i = 0; i < m; i ++){
//因为height[n]为-1,所以里层j loop完之后stack里面都会被push进n,是没有用的.
//所以这里重新new一个stack.
            s = new Stack<>();
            for (int j = 0; j < n + 1; j ++){
                if (j < n){//对于最后一个heights[n] == -1不需要变
                    if(matrix[i][j] == '0')
                        heights[j] = 0;
                    else heights[j] ++;
                }
//当栈为空的时候无论当前height值是什么都要加入栈里
                if (s.isEmpty() || heights[s.peek()] <= heights[j]){
                     s.push(j);
                     continue;
                 }
//当当前的index不能被加入栈里的时候,就要开始pop了
                 while(!s.isEmpty() && heights[s.peek()] > heights[j]){
                    h = heights[s.pop()];
                    pre = s.isEmpty() ? -1 : s.peek();
                    max = Math.max(max, (j - pre - 1) * h);
                }
                s.push(j);//这个一定要继续push到栈里面
            }            
        }
        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

%d bloggers like this: