LeetCode—85.最大矩形[Maximal Rectangle]——分析及代码[C++]

一、题目二、分析及代码1. 动态规划 + 柱状图最大矩形（1）思路（2）代码（3）结果 2. 动态规划（1）思路（2）代码（3）结果 三、其他

一、题目

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] 输出: 6

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximal-rectangle 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、分析及代码

1. 动态规划 + 柱状图最大矩形

（1）思路

结合上一题（柱状图最大矩形）求解思路，想到可以通过 动态规划 + 柱状图最大矩形 求解。 遍历矩阵的每一行，结合动态规划记录各个位置对应矩形的最大高度，再用上题方法求解。 复杂度：遍历 n * m，求最大矩形 n，合计 O(n^2* m)

（2）代码

class Solution { public: int largestRectangleArea(vector<int>& heights) {//求柱状图最大矩形，来源题84，复杂度O(n) stack<int> h;//只需存储下标，高度可从heights中直接读出 heights.push_back(0);//用于遍历完heights中所给元素后，清空栈 int ans = 0, hsize = heights.size(); for (int i = 0; i < hsize; i++) { while (!h.empty() && heights[h.top()] > heights[i]) { int top = h.top(); h.pop(); ans = max(ans, heights[top] * (h.empty() ? i : (i - h.top() - 1)));//用前一元素的下标计算 } h.push(i); } return ans; } int maximalRectangle(vector<vector<char>>& matrix) { if (matrix.empty()) return 0; int n = matrix.size(), m = matrix[0].size(), ans = 0; vector<vector<int>>num(n, vector<int>(m, 0));//记录各个位置矩形高度 for (int j = 0; j < m; j++) {//按列遍历，求解各个位置矩形高度 num[0][j] = (matrix[0][j] == '0') ? 0 : 1; for (int i = 1; i < n; i++) num[i][j] = (matrix[i][j] == '0') ? 0 : num[i - 1][j] + 1; } for (int i = 0; i < n; i++) {//按行遍历，求解各行柱状图最大矩形 int area = largestRectangleArea(num[i]); ans = max(ans, area); } return ans; } };

（3）结果

执行用时 ：28 ms, 在所有 C++ 提交中击败了 68.63% 的用户； 内存消耗 ：13 MB, 在所有 C++ 提交中击败了 12.55% 的用户。

2. 动态规划

（1）思路

用 h、l、r 分别记录每个位置对应的最大高度，和该高度所能扩展到的左右边界（左闭右开），则该位置对应的最大矩形为：h * (r - l)。 按行遍历，只需一维数组进行记录，通过动态规划求解各个位置的 h、l、r 。 1）h 求解：（遍历顺序无关） 若矩阵值为1，h[j] = h[j - 1]++； 若矩阵值为0，h[j] = 0； 2）l 求解：（从左往右遍历，l 为闭区间，初始值为 0） 设计一个 l_min 记录当前非0的最左边界，则 若矩阵值为1，l[j] = max(l[j], l_min)； 若矩阵值为0，l[j] = 0（下行时只需值不为0的位置即可成为左边界），l_min = j + 1（最左边界更新为位置右侧）; 3）r求解：（从右往左遍历，r 为开区间，初始值为 m） 设计一个 r_max 记录当前非0的最右边界，则 若矩阵值为1，r[j] = min(r[j], r_max)； 若矩阵值为0，r[j] = m，r_max = j。 复杂度：一次遍历，O(mn)。

（2）代码

class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { if (matrix.empty()) return 0; int n = matrix.size(), m = matrix[0].size(), ans = 0; vector<int> l(m, 0);//记录最大高度对应的左边界 vector<int> r(m, m);//记录最大高度对应的右边界 vector<int> h(m, 0);//记录最大高度 for (int i = 0; i < n; i++) { int l_min = 0, r_max = m; for (int j = 0; j < m; j++) {//求解l、h if (matrix[i][j] == '1') { h[j]++; l[j] = max(l[j], l_min); } else { h[j] = 0; l[j] = 0; l_min = j + 1; } } for (int j = m - 1; j > -1; j--) {//求解r if (matrix[i][j] == '1') { r[j] = min(r[j], r_max); } else { r[j] = m; r_max = j; } } for (int j = 0; j < m; j++) {//计算面积 int area = h[j] * (r[j] - l[j]); ans = max(area, ans); } } return ans; } };

（3）结果

执行用时 ：16 ms, 在所有 C++ 提交中击败了 98.88% 的用户； 内存消耗 ：10.5 MB, 在所有 C++ 提交中击败了 95.44% 的用户。

三、其他

暂无。