Leetcode 85 - Maximal Rectangle（dp）

2019-11-10 17:01:15

字体：大中小

来源：转载

供稿：网友

题意

给定一个由01组成的矩形，要求找出矩形内由1组成的面积最大的矩形面积。

思路

之前写过一道类似的题，由若干个长度为1，高度不同的矩形连在一起，求最大矩形面积。这道题其实是类似的，我们只需要预处理出在位置[i, j]上，最大的1的高度，然后一行一行的处理，就和之前那道题相同了。

状态表示：

h[i,j] $h[i, j]$ ，位置[i, j]上1的最大高度。

l[i,j] $l[i, j]$ ，位置[i, j]上，以h[i, j]为高度能向左延伸多少。

r[i,j] $r[i, j]$ ，在位置[i, j]上，以当前高度能向右延伸多少。

转移方程：

h[i,j] $h[i, j]$ 直接预处理一下即可。

l[i,j] $l[i, j]$ ：

h[i,j]>h[i,j−1] $h[i, j] > h[i, j - 1]$ : l[i,j]=1 $l[i, j] = 1$ h[i,j]≤h[i,j−1] $h[i, j] /leq h[i, j- 1]$ : l[i,j]=1+l[i][j−1] $l[i, j] = 1 + l[i][j - 1]$ 再累加上j−1−l[i][j−1] $j - 1-l[i][j - 1]$ 之前的所有高度大于h[i,j] $h[i, j]$ 的。

r[i,j] $r[i, j]$ ：

计算方法同l[i,j] $l[i, j]$

代码

const int maxn = 505;class Solution {public: int h[maxn][maxn], l[maxn][maxn], r[maxn][maxn]; int maximalRectangle(vector<vector<char>>& matrix) { int m = matrix.size(); if (m) { int n = matrix[0].size(); int res = 0; //init height for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == '1') { h[i][j] = i ? h[i - 1][j] + 1 : 1; } else { h[i][j] = 0; } } } //calculate l[j] && r[j]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { l[i][j] = 1; int t = j - 1; while (t >= 0 && h[i][j] <= h[i][t]) { l[i][j] += l[i][t]; t -= l[i][t]; } } for (int j = n - 1; j >= 0; j--) { r[i][j] = 1; int t = j + 1; while (t < n && h[i][j] <= h[i][t]) { r[i][j] += r[i][t]; t += r[i][t]; } res = max(res, h[i][j] * (l[i][j] + r[i][j] - 1)); } } return res; } return 0; }};

上一篇：继承与派生（一）

下一篇：155. Min Stack / 225. Implement Stack using Queues

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注