Index
最大矩形
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
分析：
- height[j] 表示 第j列连续字符’1’的高度，该高度按行进行更新
- left[j] 表示第j列，高度为height[j]的左边界
- right[j] 表示第j列，高度为height[j]的右边界
- 时间复杂度：O(mn)
- 空间复杂度：O(n)
int maximalRectangle(vector<vector<char>>& mat) {
int m = mat.size(), n = m ? mat[0].size() : 0;
vector<int> left(n, 0), right(n, n), height(n, 0);
int ans = 0;
for (int i = 0; i < m; ++i) {
int cur_left = 0, cur_right = n;
for (int j = 0; j < n; ++j) {
if (mat[i][j] == '1') {
height[j] = height[j] + 1;
left[j] = max(left[j], cur_left);
} else {
left[j] = height[j] = 0; cur_left = j + 1;
}
}
for (int j = n - 1; j >= 0; --j) {
if (mat[i][j] == '1') right[j] = min(right[j], cur_right);
else {
right[j] = n; cur_right = j;
}
}
for (int j = 0; j < n; ++j)
ans = max(ans, (right[j] - left[j]) * height[j]);
}
return ans;
}
使用单调栈维护的left和right
int maximalRectangle(vector<vector<char>>& mat) {
int n = mat.size(), m = n ? mat[0].size() : 0, ans = 0;
vector<int> height(m);
for (int i = 0; i < n; ++i) {
vector<int> left(m, -1), right(m, m);
stack<int> sk;
for (int j = 0; j < m; ++j) {
height[j] = mat[i][j] == '1' ? height[j] + 1 : 0;
}
for (int j = 0; j < m; ++j) {
while (!sk.empty() && height[sk.top()] > height[j]) {
right[sk.top()] = j;
sk.pop();
}
sk.push(j);
}
sk = stack<int>();
for (int j = m - 1; j >= 0; --j) {
while (!sk.empty() && height[sk.top()] > height[j]) {
left[sk.top()] = j;
sk.pop();
}
sk.push(j);
}
for (int j = 0; j < m; ++j) {
ans = max(ans, height[j] * (right[j] - left[j] - 1));
}
}
return ans;
}
柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
分析:
- height[j] 表示 第j列的高度
- left[j] 小于等于j且高度不小于height[j]的最小的j
- right[j] 大于等于j且高度不小于height[j]的最大的j
int largestRectangleArea(vector<int>& height) {
int n = height.size(), ans = 0;
vector<int> left(n, 0), right(n, 0);
for (int i = 0; i < n; ++i) {
int l = i - 1;
while (l >=0 && height[l] >= height[i]) l = left[l] - 1;
left[i] = l + 1;
}
for (int i = n - 1; i >= 0; --i) {
int r = i + 1;
while (r < n && height[r] >= height[i]) r = right[r] + 1;
right[i] = r - 1;
ans = max(ans, (right[i] - left[i] + 1) * height[i]);
}
return ans;
}
最大正方形
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
分析：动态规划
dp[i][j] 表示以(i,j)为正方形右下角的最大边长，则：
dp[i][j] = min(dp[i-1][j-1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
int maximalSquare(vector<vector<char>>& mat) {
int n = mat.size(), m = n ? mat[0].size() : 0, ans = 0;
vector<vector<int>> dp(n, vector<int>(m, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (mat[i][j] == '1') {
if (!i || !j) dp[i][j] = 1;
else {
dp[i][j] = min(dp[i-1][j-1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
ans = max(ans, dp[i][j]);
}
}
}
return ans * ans;
}
最大子矩阵
给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
vector<int> getMaxMatrix(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size(), maxsum = INT_MIN;
vector<vector<int>> sum(n + 1,vector<int>(m + 1, 0));
vector<int> ans;
for(int i = 0; i < n; ++i){
for(int j = 0,t = 0; j < m; ++j){
t += mat[i][j];
sum[i+1][j+1] = sum[i][j+1]+t;
}
}
for(int i = 1; i <= n; ++i){
for(int j = i; j <= n; ++j){
for(int k = 1,pre = 0; k <= m; ++k){
int tmp = sum[j][k]-sum[i-1][k]-sum[j][pre]+sum[i-1][pre];
if(tmp > maxsum){
maxsum = tmp;
ans = {i - 1, pre, j - 1, k - 1};
}
if(tmp <= 0) pre = k;
}
}
}
return ans;
}
矩形区域不超过k的最大数值和
给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。
int maxSumSubmatrix(vector<vector<int>>& mat, int k) {
int n = mat.size(), m = n ? mat[0].size() : 0, res = INT_MIN;
for (int l = 0; l < m; ++l) {
vector<int> sums(n, 0);
for (int r = l; r < m; ++r) {
for (int i = 0; i < n; ++i) sums[i] += mat[i][r];
set<int> st; st.insert(0);
int cur_sum = 0, cur_max = INT_MIN;
for (int sum : sums) {
cur_sum += sum;
auto it = st.lower_bound(cur_sum - k);
if (it != st.end()) cur_max = max(cur_max, cur_sum - *it);
st.insert(cur_sum);
}
res = max(res, cur_max);
}
}
return res;
}
可将一个元素变为0的最大矩形
给一个N*M的01矩阵，矩阵下标从0开始。 有Q个询问，第i个询问为：将矩阵中(x,y)的元素改为0后，只包含 1 的子矩阵的最大面积是多少。
注意
- 每次询问均是独立的。
- 询问方格内元素可能本来就是 0。
- 子矩阵的面积是指矩阵的大小。
输入
第一行包含两个整数 N,M。 接下来 N 行，每行包含 M 个 01 字符。 再一行包含整数 Q。 接下来 Q 行，每行包含 2 个整数 (xi,yi)。
输出
每个询问输出一行一个结果，表示最大面积。
数据范围
1 ≤ N,M ≤ 2000,
1 ≤ Q ≤ 1e5, 0 ≤ xi <n,0 ≤ yi <m
分析
预处理：第i行往上，第i行往下，第j列往左，第j列往右的矩形形成的最大值
每次查询一个(x,y)时，其形成的最大矩形一定在其上面或下面或左边或右边。
时间复杂度
- 预处理 O(N*M)
- 查询 O(Q)， 共 O(N*M) + O(Q)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
int n, m, Q, x, y;
char g[N][N];
int U[N], D[N], L[N], R[N], l[N], r[N], q[N], s[N][N];
int calc(int h[], int n) {
h[0] = h[n + 1] = -1;
int tt = 0, res = 0;
q[0] = 0;
for (int i = 1; i <= n; ++i) {
while (h[q[tt]] >= h[i]) tt--;
l[i] = q[tt];
q[++tt] = i;
}
tt = 0;
q[0] = n + 1;
for (int i = n; i; i--) {
while (h[q[tt]] >= h[i]) tt--;
r[i] = q[tt];
q[++tt] = i;
}
for (int i = 1; i <= n; i ++ )
res = max(res, h[i] * (r[i] - l[i] - 1));
return res;
}
//预处理，U[i]表示第i行及上面的行能组成的最大矩形，L,R,D同理。
void init(){
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ )
s[i][j] = g[i][j] == '1' ? s[i-1][j] + 1 : 0;
U[i] = max(U[i-1], calc(s[i], m));
}
memset(s, 0, sizeof s);
for (int i = n; i; --i) {
for (int j = 1; j <= m; ++j)
s[i][j] = g[i][j] == '1' ? s[i+1][j] + 1 : 0;
D[i] = max(D[i+1], calc(s[i], m));
}
memset(s, 0, sizeof s);
for (int i = 1; i <= m; i ++ ){
for (int j = 1; j <= n; j ++ )
s[i][j] = g[j][i] == '1' ? s[i-1][j] + 1 : 0;
L[i] = max(L[i-1], calc(s[i], n));
}
memset(s, 0, sizeof s);
for (int i = m; i; i-- ){
for (int j = 1; j <= n; j ++ )
s[i][j] = g[j][i] == '1' ? s[i+1][j] + 1 : 0;
R[i] = max(R[i+1], calc(s[i], n));
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1);
init();
scanf("%d", &Q);
while (Q -- ){
scanf("%d%d", &x, &y);
x++, y++; //数组下标从1开始
printf("%d\n",max(max(U[x-1], D[x+1]), max(L[y-1], R[y+1])));
}
}
