剑指offer

剑指offer,第1张

剑指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,如果为零,则当前列的值直接清零。

以此列推即可。

参考链接:

力扣

欢迎分享,转载请注明来源:内存溢出

原文地址: http://www.outofmemory.cn/zaji/5703181.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存