题目描述
给定一个 $N×M$ 的 $01$ 矩阵,矩阵下标从 $0$ 开始。
有 $Q$ 个询问,第 $i$ 个询问为:将矩阵中 $(x_i,y_i)$ 的元素改成 $0$ 之后,只包含 $1$ 的子矩阵的最大面积是多少。
注意
每次询问均是独立的。
询问方格内元素可能本来就是 $0$。
子矩阵的面积是指矩阵的大小。
输入格式
第一行包含两个整数 $N,M$。
接下来 $N$ 行,每行包含 $M$ 个 $01$ 字符。
再一行包含整数 $Q$。
接下来 $Q$ 行,每行包含 $2$ 个整数 $(x_i,y_i)$。
输出格式
每个询问输出一行一个结果,表示最大面积。
数据范围
对于 $20\%$ 的数据,$1≤N,M,Q≤10$
对于 $50\%$ 的数据,$1≤N,M,Q≤100$
对于 $100\%$ 的数据,$1≤N,M≤2000,1≤Q≤10^5, 0≤x_i<n,0≤y_i<m$
输入样例
4 2
10
11
11
11
3
0 0
2 0
3 1
输出样例
6
3
4
算法1
(动态规划 + 单调栈)
- 利用动态规划预处理出上下左右四个方向中值为
1
的方块能堆积的最大高度,将问题转化为LeetCode85.最大矩形,h[i][j]
表示以(i, j)
为底的1
所能堆积出的最大高度,然后对四个方向自上而下逐层求出能构成的最大矩形面积,记为up
,down
,left
,right
,其中up[i]
为以第i
行为底,能构成的最大矩形面积,其余方向同理。 - 由于每个询问会去掉一个格子,假设被去掉的格子是
(i,j)
,我们只需要统计up[i-1]
,down[i+1]
,left[j-1]
,right[j+1]
,并取最大值即可,注意要判断是否越界。 - 对于每一层所构成的直方图,对于每一叠
1
,我们可以通过向左右扩展找到其最远边界来求最大矩形面积,具体地:- 对于
h[i]
,找到左侧第一个比h[i]
小的位置,其右侧第一个数就是向左扩展到的最远距离 - 对于
h[i]
,找到右侧第一个比h[i]
小的位置,其左侧第一个数就是向右扩展到的最远距离
- 对于
- 对于求左右侧第一个比当前元素小的位置,可以用单调递增的栈来线性维护,具体实现见代码
Java 代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
char[][] mat = new char[n][m];
for(int i = 0; i < n; i++){
String line = sc.next();
for(int j = 0; j < m; j++){
mat[i][j] = line.charAt(j);
}
}
int N = 2010;
int[] left = new int[N], right = new int[N], up = new int[N], down = new int[N];
int[][] h = new int[N][N];
//上侧
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(mat[i][j] == '1'){
if(i > 0) h[i][j] = h[i - 1][j] + 1;
else h[i][j] = 1;
}
}
up[i] = maxArea(h[i], m);
if(i > 0) up[i] = Math.max(up[i - 1], up[i]);
}
// 清空
for(int[] hh: h) Arrays.fill(hh, 0);
// 下侧
for(int i = n - 1; i >= 0; i--){
for(int j = 0; j < m; j++){
if(mat[i][j] == '1'){
if(i < n - 1) h[i][j] = h[i + 1][j] + 1;
else h[i][j] = 1;
}
}
down[i] = maxArea(h[i], m);
if(i < n - 1) down[i] = Math.max(down[i + 1], down[i]);
}
// 清空
for(int[] hh: h) Arrays.fill(hh, 0);
// 左侧
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(mat[j][i] == '1'){
if(i > 0) h[i][j] = h[i - 1][j] + 1;
else h[i][j] = 1;
}
}
left[i] = maxArea(h[i], n);
if(i > 0) left[i] = Math.max(left[i - 1], left[i]);
}
// 清空
for(int[] hh: h) Arrays.fill(hh, 0);
// 右侧
for(int i = m-1; i >= 0; i--){
for(int j = 0; j < n; j++){
if(mat[j][i] == '1'){
if(i < m - 1) h[i][j] = h[i + 1][j] + 1;
else h[i][j] = 1;
}
}
right[i] = maxArea(h[i], n);
if(i < m - 1) right[i] = Math.max(right[i + 1], right[i]);
}
int q = sc.nextInt();
for(int i = 0; i < q; i++){
int res = 0;
int x = sc.nextInt(), y = sc.nextInt();
if(x > 0) res = Math.max(res, up[x - 1]);
if(x < n - 1) res = Math.max(res, down[x + 1]);
if(y > 0) res = Math.max(res, left[y - 1]);
if(y < m - 1) res = Math.max(res, right[y + 1]);
System.out.println(res);
}
}
static int maxArea(int[] h, int n){
int[] l = new int[n];
int[] r = new int[n];
Deque<Integer> stk = new ArrayDeque<>();
for(int i = 0; i < n; i++){
while(stk.size() > 0 && h[stk.peek()] >= h[i]) stk.pop();
l[i] = stk.size() == 0 ? 0 : stk.peek() + 1;
stk.push(i);
}
stk.clear();
for(int i = n - 1; i >= 0; i--){
while(stk.size() > 0 && h[stk.peek()] >= h[i]) stk.pop();
r[i] = stk.size() == 0 ? n - 1 : stk.peek() - 1;
stk.push(i);
}
int maxv = 0;
for(int i = 0; i < n; i++){
maxv = Math.max(maxv, (r[i] - l[i] + 1) * h[i]);
}
return maxv;
}
}
- 时间复杂度:$O(n \times m + q)$