85. Maximal Rectangle 由1拼出的最大矩形

［抄题］：

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

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

二为矩阵：2个0，一个null

［思维问题］：

［英文数据结构或算法，为什么不用别的数据结构或算法］：

stack：把长度最长的列号暂存，然后取出来进行面积的比较

［一句话思路］：

新h[i]比旧h[i]长才能进,等于也行.

随着i的递增，旧h[i]比新h[i]长才用比较面积

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

h[]数组表示的是纵向长度，里面的index应该是横向坐标 cLen。多开辟一列并且初始化为0，用于POP stack中之前的元素

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

stack中只存最之前和现在最长的

［复杂度］：Time complexity: O(n^2) Space complexity: O(n)

［算法思想：递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

dp is 2 hard

［Follow Up］：

［LC给出的题目变变变］：

84 histogram

[代码风格] ：

class Solution {

    public int maximalRectangle(char[][] matrix) {

        //cc

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;

        //ini: cLen, rLen, Stack : for longest index, h[rLen + 1]

        int rLen = matrix.length, cLen = matrix[0].length, max = 0;

        int[] h = new int[cLen + 1];

        h[cLen] = 0;

        //for loop: row (new stack) * col < cLen + 1

        for (int row = 0; row < rLen; row++) {

            Stack<Integer> stack = new Stack<Integer>();

            for (int i = 0; i < cLen + 1; i++) {

                //store h[i]

                if (i < cLen)

                    if (matrix[row][i] == '1') h[i] += 1;

                    else h[i] = 0;

                //store i, compare area, add i to stack again

                if (stack.isEmpty() || h[i] >= h[stack.peek()])

                    //新比旧长才能进,等于也行

                    stack.push(i);

                else {

                    while (!stack.isEmpty() && h[i] < h[stack.peek()]) {//旧比新长才用比较

                        int top = stack.pop();

                        int area = h[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);

                        max = Math.max(max, area);

                    }

                    stack.push(i);

                }

            }

        }

        return max;

    }

}

巴特西

85. Maximal Rectangle 由1拼出的最大矩形

最新文章

热门文章