LeetCode每日一题：maximal rectangle

问题描述

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

问题分析

这道题可以说是上一道的延伸，把一维数组改成了二维数组，我们可以使用上一题的方法，把二维数组的每一行作为输入，输入的高度就是该行向上连在一起的‘1’高度，循环row行最后取最大值即可。

代码实现

    public int largestRectangleArea(int[] height) {
        if (height.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for (int i = 0; i < height.length; i++) {
            if (stack.isEmpty() || stack.peek() <= height[i]) stack.push(height[i]);
            else {
                int count = 0;
                while (!stack.isEmpty() && stack.peek() > height[i]) {
                    count++;
                    result = Math.max(result, stack.peek() * count);
                    stack.pop();
                }
                while (count > 0) {
                    count--;
                    stack.push(height[i]);
                }
                stack.push(height[i]);
            }
        }
        int depth = 1;
        while (!stack.isEmpty()) {
            result = Math.max(result, stack.peek() * depth);
            stack.pop();
            depth++;
        }
        return result;
    }

    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int result = 0;
        for (int i = 0; i < row; i++) {
            int[] num = new int[col];
            Arrays.fill(num, 0);
            for (int j = 0; j < col; j++) {
                int k = i;
                while (k >= 0 && matrix[k][j] == '1') {
                    num[j]++;
                    k--;
                }

            }
            result = Math.max(result, largestRectangleArea(num));
        }
        return result;
    }