【每日一题】LeetCode 363.矩形区域不超过K的最大数值和

本文最后更新于:2021年4月22日 晚上

LeetCode 363. 矩形区域不超过K的最大数值和

思路

将问题转化为一维上的问题,枚举lohi表示当前处理数据的列区间,对于每一个列区间,可以看做一个一维问题。
一维问题可以用前缀和配合二分的方式在 O(mlog⁡m) 的时间解决。维护一个有序集合,集合中初始放入 0。每次获取当前位置的前缀和,在集合中二分查找第一个大于等于 sum - k 的数字,如果能找到,则更新答案。然后将当前位置的前缀和放入有序集合中。
由此推出的列区间共有n^2个。每个一维问题解决时间为O(mlogm),故总时间复杂度为O(n^2mlog(m))

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
vector<vector<int>> s;

int get(int x1,int y1,int x2,int y2)
{
return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int n=matrix.size(), m=matrix[0].size();
s=vector<vector<int>>(n+1, vector<int>(m+1));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+matrix[i-1][j-1];
int res=INT_MIN;
for(int i=1;i<=m;i++)
{
for(int j=i;j<=m;j++)
{
set<int> S;
S.insert(0);
for(int p=1;p<=n;p++)
{
int si=get(1,i,p,j);
auto it=S.lower_bound(si-k);
if(it!=S.end()) res=max(res, si-*it);
S.insert(si);
}
}
}
return res;
}
};

AcWing 3412.邻域均值

思路

使用前缀和,得出最后的s[N][N]然后进行计算,后面主要返回整体的平均值即可,每次都选出最适合的区域并保存。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=610;

int n,L,r,t;
int s[N][N];

int get_sum(int x1,int y1,int x2,int y2)
{
return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}

int get_cnt(int x1,int y1,int x2,int y2)
{
return (x2-x1+1)*(y2-y1+1);
}

int main()
{
cin>>n>>L>>r>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x;
cin>>x;
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
}
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x1=max(1, i-r), y1=max(1, j-r);
int x2=min(n, i+r), y2=min(n, j+r);
if(get_sum(x1,y1,x2,y2)<=t * get_cnt(x1,y1,x2,y2))
res++;
}
cout<<res<<endl;
return 0;
}