题目描述
给定一个 N×M 的 01 矩阵,矩阵下标从 0 开始。
有 Q 个询问,第 i 个询问为:将矩阵中 (xi,yi) 的元素改成 0 之后,只包含 1 的子矩阵的最大面积是多少。
注意:
每次询问均是独立的。
询问方格内元素可能本来就是 0。
子矩阵的面积是指矩阵的大小。
输入格式
第一行包含两个整数 N,M。
接下来 N 行,每行包含 M 个 01 字符。
再一行包含整数 Q。
接下来 Q 行,每行包含 2 个整数 (xi,yi)。
输出格式
每个询问输出一行一个结果,表示最大面积。
数据范围
对于 20% 的数据,1≤N,M,Q≤10
对于 50% 的数据,1≤N,M,Q≤100
对于 100% 的数据,1≤N,M≤2000,1≤Q≤105, 0≤xi<n,0≤yi<m
样例
输入样例:
4 2
10
11
11
11
3
0 0
2 0
3 1
输出样例:
6
3
4
算法1
(单调栈,前缀数组) $O(n^2)$
做不出来。y总讲解了以后,发现自己太菜了
不是什么大佬。就是想把代码贴一下。自己做个纪念。没听y总的讲课的小伙伴可以看一下。
毕竟python3的代码相对cpp 少一点。 大家(佬)都用c++
c++代码TLE了。我还没调过。可能是用了vector的缘故。还有调用了stack的缘故,没有手动模拟
(我不会用int [][] …………没背板子)
时间复杂度
参考文献
python3 代码
[Row, Col] = [int(x) for x in input().split()]
grid = [[] for _ in range(Row)]
for r in range(Row):
line = list(input())
grid[r] = [int(x) for x in line]
Q = int(input())
queries = []
for _ in range(Q):
queries.append([int(x) for x in input().split()])
def calc(height, n: int) -> int: #直方图中最大的矩形 LeetCode 84,85
height = [-1] + height + [-1] #2个哨兵
res = 0
inc_stk = [] #单调递增栈
for i in range(n + 2):
while inc_stk and height[inc_stk[-1]] > height[i]:
cur_window_min_height = height[inc_stk.pop(-1)]
window_L = inc_stk[-1] + 1
window_R = i - 1
window_area = (window_R - window_L + 1) * cur_window_min_height
res = max(res, window_area)
inc_stk.append(i)
return res
UP_pre = [0 for _ in range(Row + 1)] #从上往下,前r行(从1开始)的最大矩形面积
height = [0 for _ in range(Col)]
for r in range(Row):
for c in range(Col):
if grid[r][c] == 1:
height[c] += 1
else:
height[c] = 0
UP_pre[r + 1] = max(UP_pre[r], calc(height, Col) )
DOWN_pre = [0 for _ in range(Row + 1)] #从下往上,前r行的最大矩形面积
height = [0 for _ in range(Col)]
for r in range(Row - 1, -1, -1):
for c in range(Col):
if grid[r][c] == 1:
height[c] += 1
else:
height[c] = 0
DOWN_pre[r] = max(DOWN_pre[r+1], calc(height, Col))
Left_pre = [0 for _ in range(Col + 1)] #从左往右,前c列的最大矩形面积
height = [0 for _ in range(Row)]
for c in range(Col):
for r in range(Row):
if grid[r][c] == 1:
height[r] += 1
else:
height[r] = 0
Left_pre[c+1] = max(Left_pre[c], calc(height, Row))
Right_pre = [0 for _ in range(Col + 1)] #从右往左,前c列的最大矩形面积
height = [0 for _ in range(Row)]
for c in range(Col - 1, -1, -1):
for r in range(Row):
if grid[r][c] == 1:
height[r] += 1
else:
height[r] = 0
Right_pre[c] = max(Right_pre[c + 1], calc(height, Row))
# print(UP_pre)
# print(DOWN_pre)
# print(Left_pre)
# print(Right_pre)
for qr, qc in queries:
res = max(UP_pre[qr], DOWN_pre[qr+1], Left_pre[qc], Right_pre[qc+1])
print(res)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int calc(vector<int> height, int n) //直方图中最大的矩形 LeetCode 84,85
{
height.insert(height.begin(), -1);
height.push_back(-1); //2个哨兵
int res = 0;
stack<int> inc_stk; //单调递增栈
for (int i = 0; i < n + 2; i ++)
{
while (inc_stk.size() && (height[inc_stk.top()] > height[i]))
{
int window_min_height = height[inc_stk.top()];
inc_stk.pop();
int window_L = inc_stk.top() + 1;
int window_R = i - 1;
int window_area = (window_R - window_L + 1) * window_min_height;
res = max(res, window_area);
}
inc_stk.push(i);
}
return res;
}
int main()
{
int Row; cin >> Row;
int Col; cin >> Col;
vector<vector<int>> grid(Row, vector<int>(Col, 0));
char chr;
for (int r = 0; r < Row; r ++)
for (int c = 0; c < Col; c ++)
{
cin >> chr;
grid[r][c] = (chr - '0');
}
vector<int> height(Col, 0);
vector<int> UP_pre(Row + 1, 0); //从上往下,前r行(从1开始)的最大矩形面积
for (int r = 0; r < Row; r ++)
{
for(int c = 0; c < Col; c ++)
{
if (grid[r][c] == 1 )
height[c] += 1;
else
height[c] = 0;
}
UP_pre[r+1] = max(UP_pre[r], calc(height, Col));
}
// for (int x: UP_pre) cout << x << endl;
vector<int> height2(Col, 0);
vector<int> DOWN_pre(Row + 1, 0); //从下往上,前r行(从1开始)的最大矩形面积
for (int r = Row - 1; r > -1; r --)
{
for (int c = 0; c < Col; c ++)
{
if (grid[r][c] == 1)
height2[c] ++;
else
height2[c] = 0;
}
DOWN_pre[r] = max(DOWN_pre[r + 1], calc(height2, Col));
}
// for (int x: DOWN_pre) cout << x << endl;
vector<int> height3(Row, 0);
vector<int> Left_pre(Col + 1, 0); //从左往右,前c列(从1开始)的最大矩形面积
for (int c = 0; c < Col; c ++)
{
for (int r = 0; r < Row; r ++)
{
if (grid[r][c] == 1)
height3[r] ++;
else
height3[r] = 0;
}
Left_pre[c+1] = max(Left_pre[c], calc(height3, Row) );
}
// for (int x: Left_pre) cout << x << endl;
vector<int> height4(Row, 0);
vector<int> Right_pre(Col + 1, 0); //从右往左,前c列(从1开始)的最大矩形面积
for (int c = Col - 1; c > -1; c --)
{
for (int r = 0; r < Row; r ++)
{
if (grid[r][c] == 1)
height4[r] ++;
else
height4[r] = 0;
}
Right_pre[c] = max(Right_pre[c + 1], calc(height4, Row));
}
// for (int x: Right_pre) cout << x << endl;
int Q; cin >> Q;
for (int _ = 0; _ < Q; _ ++)
{
int qr; cin >> qr;
int qc; cin >> qc;
int res = max(max(UP_pre[qr], DOWN_pre[qr + 1]), max(Left_pre[qc], Right_pre[qc + 1]));
cout << res << endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
嗯 谢谢啦
我自己实现用stack实现单调栈也超时了,用y总写的单调栈就没有超时,大佬知道原因吗?
我不是大佬。我刚来acwing。y总和大佬们都是int [] 手动模拟栈,自己造轮子,都是背模板,运行起来肯定飞快。调STL尤其像stack[HTML_REMOVED] vector[HTML_REMOVED]就会很慢很慢。
我是用python3的;c++只会写一丢丢,只会做题常用的东西