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

  • leetcode
  • acwing
  • 每日一题
  • 算法
    abbrlink: 95003eb
    date: 2021-04-22 19:00:28

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

思路

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

C++代码

  1. class Solution {
  2. public:
  3.     vector<vector<int>> s;
  5.     int get(int x1,int y1,int x2,int y2)
  6.     {
  7.         return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
  8.     }
  9.     int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
  10.         int n=matrix.size(), m=matrix[0].size();
  11.         s=vector<vector<int>>(n+1, vector<int>(m+1));
  12.         for(int i=1;i<=n;i++)
  13.             for(int j=1;j<=m;j++)
  14.                 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+matrix[i-1][j-1];
  15.         int res=INT_MIN;
  16.         for(int i=1;i<=m;i++)
  17.         {
  18.             for(int j=i;j<=m;j++)
  19.             {
  20.                 set<int> S;
  21.                 S.insert(0);
  22.                 for(int p=1;p<=n;p++)
  23.                 {
  24.                     int si=get(1,i,p,j);
  25.                     auto it=S.lower_bound(si-k);
  26.                     if(it!=S.end()) res=max(res, si-*it);
  27.                     S.insert(si);
  28.                 }
  29.             }
  30.         }
  31.         return res;
  32.     }
  33. };

AcWing 3412.邻域均值

思路

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

C++代码

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  5. using namespace std;
  7. const int N=610;
  9. int n,L,r,t;
  10. int s[N][N];
  12. int get_sum(int x1,int y1,int x2,int y2)
  13. {
  14.     return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
  15. }
  17. int get_cnt(int x1,int y1,int x2,int y2)
  18. {
  19.     return (x2-x1+1)*(y2-y1+1);
  20. }
  22. int main()
  23. {
  24.     cin>>n>>L>>r>>t;
  25.     for(int i=1;i<=n;i++)
  26.         for(int j=1;j<=n;j++)
  27.         {
  28.             int x;
  29.             cin>>x;
  30.             s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
  31.         }
  32.     int res=0;
  33.     for(int i=1;i<=n;i++)
  34.         for(int j=1;j<=n;j++)
  35.         {
  36.             int x1=max(1, i-r), y1=max(1, j-r);
  37.             int x2=min(n, i+r), y2=min(n, j+r);
  38.             if(get_sum(x1,y1,x2,y2)<=t * get_cnt(x1,y1,x2,y2))
  39.                 res++;
  40.         }
  41.     cout<<res<<endl;
  42.     return 0;
  43. }