剑指offer

剑指offer 题目：

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix 输入格式为一维 01 字符串数组。

示例 1：

输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = ["0"]
输出：0

示例 4：

输入：matrix = ["1"]
输出：1

示例 5：

输入：matrix = ["00"]
输出：0

提示：

rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'

代码：转换为直方图 

    class Solution {
        public static int maximalRectangle(String[] matrix) {
            if (matrix.length == 0) {
                return 0;
            }
            // 记录最大面积
            int maxArea = 0;
            // 初始化一个栈用来存储下标
            Stack stack = new Stack<>();
            // 放进去一个 -1 防止左侧没有矩形
            stack.push(-1);
            // 创建一个数组用来模拟直方图，每个元素代表一个矩形的高度
            int[] array = new int[matrix[0].length()];
            // 模拟直方图最大矩阵求解
            for (String s : matrix) {
                // 转化为直方图
                for (int i = 0; i < s.length(); i++) {
                    array[i] = s.charAt(i) - '0' == 0 ? 0 : s.charAt(i) - '0' + array[i];
                }

                // 求直方图最大面积
                for (int i = 0; i < array.length; i++) {
                    while (stack.peek() != -1 && array[stack.peek()] > array[i]) {
                        int height = array[stack.pop()];
                        int width = i - stack.peek() - 1;
                        maxArea = Math.max(maxArea, height * width);
                    }
                    stack.push(i);
                }
                while (stack.peek() != -1) {
                    int height = array[stack.pop()];
                    int width = array.length - stack.peek() - 1;
                    maxArea = Math.max(maxArea, height * width);
                }
            }
            return maxArea;
        }
    }

解题思路：

本题的主要思想是把矩阵转换为直方图，转换为直方图以后的 *** 作与上题一致，所以这里只说下转换为直方图的思想。

转换为直方图的思想较为巧妙。

第一次只看第一行，每一列看成一个矩形，然后对这些矩形求最大面积。并更新maxArea。

第二次看第一行和第二行组合在一起，还是每一列看成矩形，然后对这些矩形求最大面积，并更新maxArea。组合的时候，会更新每一列的值，也就是矩形的高，更新规则是，如果最新组合进来的一行当前列为1，则在原来的列的基础上加1，如果为零，则当前列的值直接清零。

以此列推即可。

参考链接：

力扣