LeetCode 85. Maximal Rectangle

題目來源：https://leetcode.com/problems/maximal-rectangle/

問題描述

85. Maximal Rectangle

Hard

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

Example:

Input:

[

  ["1","0","1","0","0"],

  ["1","0","1","1","1"],

  ["1","1","1","1","1"],

  ["1","0","0","1","0"]

]

Output: 6

------------------------------------------------------------

題意

一個矩陣全由’0’和’1’組成，求其中最大的全’1’矩形的面積。

------------------------------------------------------------

思路

【思路1】

作為LeetCode 84. Largest Rectangle in Histogram的擴充，将每行看作一個直方圖求最大矩形問題求解，再求所有行的結果的最大值。矩形和行直方圖的對應關系由以下例子示範：

1	1
1	1	1	1
1	1	1	1	1
1	1

對應如下行直方圖表，第i行是原矩陣的[0:i]行累積成的直方圖。

1	1
2	2	1	1
3	1	3	2	2
4	3

由于每行的直方圖求最大矩形的複雜度為O(n)，故總複雜度為O(n^2)，但該方法常數較大。

【思路2】

還是對原矩形每行進行掃描，同時維護每行n個格點的三個數組lefts, rights, heights分别表示該格點所在矩形的最左、最右、最上邊界。同時每行維護兩個整數ones_left和ones_right，表示目前格點在本行的最邊界和右邊界（用便于面積計算，右邊界實際上加了1）。

最左邊界的預設值是0，最右邊界的預設值是n。每行周遊過程中從左到右更新lefts，同時從右到左更新rights。以lefts[j]和ones_left的更新為例，對于格點matrix[i][j]，

• 如果matrix[i][j]=1，則考察上一行的lefts[j]，
  1. 如果上一行的lefts[i]是預設值0，表示上一行matrix[i-1][j]=0，則本行的lefts[j]表示本行的矩形邊界，
  2. 如果上一行lefts[j]不是0，表示上一行matrix[i-1][j]=1，則本行的lefts[j]表示和上一行共同組成的矩形的邊界。
• 如果matrix[i][j]=0，則将lefts[j]置零表示本行j處是0，同時更新ones_left=j+1，表示對于matrix[i][j+1]來說，最左邊的1至少在j+1處（當然即使matrix[i][j+1]=0，也不影響，因為此時ones_left又被更新為j+2了）

------------------------------------------------------------

代碼

【解法1】

class Solution {
    class Pair {
        int height, cnt;
        
        public Pair(int height, int cnt)
        {
            this.height = height;
            this.cnt = cnt;
        }
    }
    
    private int largestRectangleArea(int[] heights) {
        Stack<Pair> stack = new Stack<Pair>();
        int maxSize = 0, curSize = 0, curCnt = 0;
        for (int h: heights)
        {
            if (stack.empty())
            {
                stack.push(new Pair(h, 1));
            }
            else if (h == stack.peek().height)
            {
                stack.peek().cnt++;
            }
            else if (h > stack.peek().height)
            {
                stack.push(new Pair(h, 1));
            }
            else
            {
                Pair poped = stack.pop();
                curCnt = poped.cnt;
                curSize = poped.height*curCnt;
                maxSize = curSize>maxSize?curSize:maxSize;
                while (!stack.empty() && h < stack.peek().height)
                {
                    poped = stack.pop();
                    curCnt += poped.cnt;
                    curSize = poped.height*curCnt;
                    maxSize = curSize>maxSize?curSize:maxSize;
                }
                if (stack.empty())
                {
                    stack.push(new Pair(h, curCnt+1));
                }
                else if (stack.peek().height == h)
                {
                    stack.peek().cnt += curCnt+1;
                }
                else
                {
                    stack.push(new Pair(h, curCnt+1));
                }
            }
        }
        curCnt = 0;
        while (!stack.empty())
        {
            Pair poped = stack.pop();
            curCnt += poped.cnt;
            curSize = curCnt*poped.height;
            maxSize = curSize>maxSize?curSize:maxSize;
        }
        return maxSize;
    }
    
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0)
        {
            return 0;
        }
        int n = matrix[0].length;
        int maxSize = 0, curSize = 0;
        int[] heights = new int[n];
        for (int i=0; i<m; i++)
        {
            for (int j=0; j<n; j++)
            {
                if (matrix[i][j] == '1')
                {
                    heights[j] += 1;
                }
                else
                {
                    heights[j] = 0;
                }
            }
            curSize = largestRectangleArea(heights);
            maxSize = curSize>maxSize?curSize:maxSize;
        }
        return maxSize;
    }
}
           

【解法2】

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0)
        {
            return 0;
        }
        int n = matrix[0].length, i = 0, j = 0, ones_left = 0, ones_right = n;
        int maxSize = 0, curSize = 0;
        int[] lefts = new int[n];       // left bound of matrix[i][j]
        int[] rights = new int[n];      // right bound of matrix[i][j]
        Arrays.fill(rights, n);
        int[] heights = new int[n];     // height of matrix[i][j]
        for (i=0; i<m; i++)         // iterate over rows
        {
            ones_left = 0;
            ones_right = n;
            // update heights
            for (j=0; j<n; j++)
            {
                if (matrix[i][j] == '1')
                {
                    heights[j]++;
                }
                else
                {
                    heights[j] = 0;
                }
            }
            // update lefts
            for (j=0; j<n; j++)
            {
                if (matrix[i][j] == '1')
                {
                    lefts[j] = ones_left > lefts[j]? ones_left: lefts[j];
                }
                else
                {
                    lefts[j] = 0;
                    ones_left = j+1;
                }
            }
            // update rights
            for (j=n-1; j>=0; j--)
            {
                if (matrix[i][j] == '1')
                {
                    rights[j] = ones_right < rights[j]? ones_right: rights[j];
                }
                else
                {
                    rights[j] = n;
                    ones_right = j;
                }
            }
            // update max size
            for (j=0; j<n; j++)
            {
                maxSize = Math.max(maxSize, heights[j]*(rights[j]-lefts[j]));
            }
        }
        return maxSize;
    }
}