C++实现LeetCode(85.最大矩形)

[LeetCode] 85. Maximal Rectangle 最大矩形

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

此题是之前那道的 Largest Rectangle in Histogram 的扩展,这道题的二维矩阵每一层向上都可以看做一个直方图,输入矩阵有多少行,就可以形成多少个直方图,对每个直方图都调用 Largest Rectangle in Histogram 中的方法,就可以得到最大的矩形面积。那么这道题唯一要做的就是将每一层都当作直方图的底层,并向上构造整个直方图,由于题目限定了输入矩阵的字符只有 '0' 和 '1' 两种,所以处理起来也相对简单。方法是,对于每一个点,如果是 ‘0',则赋0,如果是 ‘1',就赋之前的 height 值加上1。具体参见代码如下:

解法一:

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int res = 0;
        vector<int> height;
        for (int i = 0; i < matrix.size(); ++i) {
            height.resize(matrix[i].size());
            for (int j = 0; j < matrix[i].size(); ++j) {
                height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);
            }
            res = max(res, largestRectangleArea(height));
        }
        return res;
    }
    int largestRectangleArea(vector<int>& height) {
        int res = 0;
        stack<int> s;
        height.push_back(0);
        for (int i = 0; i < height.size(); ++i) {
            if (s.empty() || height[s.top()] <= height[i]) s.push(i);
            else {
                int tmp = s.top(); s.pop();
                res = max(res, height[tmp] * (s.empty() ? i : (i - s.top() - 1)));
                --i;
            }
        }
        return res;
    }
};

我们也可以在一个函数内完成,这样代码看起来更加简洁一些,注意这里的 height 初始化的大小为 n+1,为什么要多一个呢?这是因为我们只有在当前位置小于等于前一个位置的高度的时候,才会去计算矩形的面积,假如最后一个位置的高度是最高的,那么我们就没法去计算并更新结果 res 了,所以要在最后再加一个高度0,这样就一定可以计算前面的矩形面积了,这跟上面解法子函数中给 height 末尾加一个0是一样的效果,参见代码如下:

解法二:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int res = 0, m = matrix.size(), n = matrix[0].size();
        vector<int> height(n + 1);
        for (int i = 0; i < m; ++i) {
            stack<int> s;
            for (int j = 0; j < n + 1; ++j) {
                if (j < n) {
                    height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
                }
                while (!s.empty() && height[s.top()] >= height[j]) {
                    int cur = s.top(); s.pop();
                    res = max(res, height[cur] * (s.empty() ? j : (j - s.top() - 1)));
                }
                s.push(j);
            }
        }
        return res;
    }
};

下面这种方法的思路很巧妙,height 数组和上面一样,这里的 left 数组表示若当前位置是1且与其相连都是1的左边界的位置(若当前 height 是0,则当前 left 一定是0),right 数组表示若当前位置是1且与其相连都是1的右边界的位置再加1(加1是为了计算长度方便,直接减去左边界位置就是长度),初始化为n(若当前 height 是0,则当前 right 一定是n),那么对于任意一行的第j个位置,矩形为 (right[j] - left[j]) * height[j],我们举个例子来说明,比如给定矩阵为:

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

第0行:

h: 1 1 0 0 1

l: 0 0 0 0 4

r: 2 2 5 5 5

第1行:

h: 0 2 0 0 2

l: 0 1 0 0 4 

r: 5 2 5 5 5

第2行:

h: 0 0 1 1 3

l: 0 0 2 2 4 

r: 5 5 5 5 5

第3行:

h: 0 0 2 2 4

l: 0 0 2 2 4 

r: 5 5 5 5 5

第4行:

h: 0 0 0 0 5

l: 0 0 0 0 4

r: 5 5 5 5 5

解法三:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int res = 0, m = matrix.size(), n = matrix[0].size();
        vector<int> height(n, 0), left(n, 0), right(n, n);
        for (int i = 0; i < m; ++i) {
            int cur_left = 0, cur_right = n;
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    ++height[j];
                    left[j] = max(left[j], cur_left);
                } else {
                    height[j] = 0;
                    left[j] = 0;
                    cur_left = j + 1;
                }
            }
            for (int j = n - 1; j >= 0; --j) {
                if (matrix[i][j] == '1') {
                    right[j] = min(right[j], cur_right);
                } else {
                    right[j] = n;
                    cur_right = j;
                }
                res = max(res, (right[j] - left[j]) * height[j]);
            }
        }
        return res;
    }
};

再来看一种解法,这里我们统计每一行的连续1的个数,使用一个数组 h_max, 其中 h_max[i][j] 表示第i行,第j个位置水平方向连续1的个数,若 matrix[i][j] 为0,那对应的 h_max[i][j] 也一定为0。统计的过程跟建立累加和数组很类似,唯一不同的是遇到0了要将 h_max 置0。这个统计好了之后,只需要再次遍历每个位置,首先每个位置的 h_max 值都先用来更新结果 res,因为高度为1也可以看作是矩形,然后我们向上方遍历,上方 (i, j-1) 位置也会有 h_max 值,但是用二者之间的较小值才能构成矩形,用新的矩形面积来更新结果 res,这样一直向上遍历,直到遇到0,或者是越界的时候停止,这样就可以找出所有的矩形了,参见代码如下:

解法四:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int res = 0, m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> h_max(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '0') continue;
                if (j > 0) h_max[i][j] = h_max[i][j - 1] + 1;
                else h_max[i][0] = 1;
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (h_max[i][j] == 0) continue;
                int mn = h_max[i][j];
                res = max(res, mn);
                for (int k = i - 1; k >= 0 && h_max[k][j] != 0; --k) {
                    mn = min(mn, h_max[k][j]);
                    res = max(res, mn * (i - k + 1));
                }
            }
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(85.最大矩形)的文章就介绍到这了,更多相关C++实现最大矩形内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(73.矩阵赋零)

    [LeetCode] 73.Set Matrix Zeroes 矩阵赋零 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably

  • C++实现LeetCode(76.最小窗口子串)

    [LeetCode] 76. Minimum Window Substring 最小窗口子串 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BA

  • C++实现LeetCode(75.颜色排序)

    [LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2

  • C++实现LeetCode(71.简化路径)

    [LeetCode] 71.Simplify Path 简化路径 Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" click to show corner cases. Corner Cases

  • C++实现LeetCode(72.编辑距离)

    [LeetCode] 72. Edit Distance 编辑距离 Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a char

  • C++实现LeetCode(74.搜索一个二维矩阵)

    [LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

  • C++实现LeetCode(79.词语搜索)

    [LeetCode] 79. Word Search 词语搜索 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. Th

  • C++实现LeetCode(85.最大矩形)

    [LeetCode] 85. Maximal Rectangle 最大矩形 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

  • C++实现LeetCode(84.直方图中最大的矩形)

    [LeetCode] 84. Largest Rectangle in Histogram 直方图中最大的矩形 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of e

  • LeetCode 单调栈内容小结

    LeetCode Monotone Stack Summary 单调栈小结 所谓的单调栈 Monotone Stack,就是栈内元素都是单调递增或者单调递减的,有时候需要严格的单调递增或递减,根据题目的具体情况来看吧.关于单调栈,这个帖子讲的不错,而且举了个排队的例子来类比.那么,博主也举个生动的例子来说明吧:比如有一天,某家店在发 free food,很多人在排队,于是你也赶过去凑热闹.但是由于来晚了,队伍已经很长了,想着不然就插个队啥的.但发现排在队伍最前面的都是一些有纹身的大佬,惹不起,只

  • C++实现LeetCode(59.螺旋矩阵之二)

    [LeetCode] 59. Spiral Matrix II 螺旋矩阵之二 Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 此题跟之前那道 Spiral Matrix 本质上没什么区别,就相当于个类似逆

  • SQL实现LeetCode(178.分数排行)

    [LeetCode] 178.Rank Scores 分数排行 Write a SQL query to rank scores. If there is a tie between two scores, both should have the same ranking. Note that after a tie, the next ranking number should be the next consecutive integer value. In other words, th

  • PHP二维数组矩形转置实例

    PHP二维数组矩形转置实例 <?php //二维数组转置 //定义一个二维数组 $arr =array(array(1,2,3),array(4,5,6)); //定义一个数组来放置转置的数据 $arr1=array(); //转置前遍历 echo "转置前:<br/>"; for($i=0;$i<count($arr);$i++){ for($j=0;$j<count($arr[$i]);$j++){ echo $arr[$i][$j]; } echo

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • Android开发使用自定义View将圆角矩形绘制在Canvas上的方法

    本文实例讲述了Android开发使用自定义View将圆角矩形绘制在Canvas上的方法.分享给大家供大家参考,具体如下: 前几天,公司一个项目中,头像图片需要添加圆角,这样UI效果会更好看,于是写了一个小的demo进行圆角的定义,该处主要是使用BitmapShader进行了渲染(如果要将一张图片裁剪成椭圆或圆形显示在屏幕上,也可以使用BitmapShader来完成). BitmapShader类完成渲染图片的基本步骤如下: 1.创建BitmapShader类的对象 /** * Call this

  • js绘制圆形和矩形的方法

    本文实例讲述了js绘制圆形和矩形的方法.分享给大家供大家参考.具体如下: 这里使用js来绘制圆形和矩形,支持选择图形的背景颜色,同时可设置圆角矩形.半径.正圆.矩形.正方形这几个选项.或许这些图形你不需要,但重要的是让你学会JavaScript绘制图形的方法,这是要表达的核心. 运行效果如下图所示: 具体代码如下: <!doctype html> <html> <head> <title>js来绘制圆形和矩形</title> <style&

  • 矩形相交以及求出相交的区域的原理解析

    (1)设计一个算法,确定两个矩形是否相交(即有重叠区域) (2)如果两个矩形相交,设计一个算法,求出相交的区域矩形 (1) 对于这个问题,一般的思路就是判断一个矩形的四个顶点是否在另一个矩形的区域内.这个思路最简单,但是效率不高,并且存在错误,错误在哪里,下面分析一 下. 如上图,把矩形的相交(区域重叠)分成三种(可能也有其他划分),对于第三种情况,如图中的(3),两个矩形相交,但并不存在一个矩形的顶点在另一个矩形 内部.所以那种思路存在一个错误,对于这种情况的相交则检查不出. 仔细观察上图,想

随机推荐