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

公众号guangcity

发布于 2021-05-08 15:31:48

4150

发布于 2021-05-08 15:31:48

文章被收录于专栏：光城(guangcity)

题目：给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

题解：

前缀和暴力

class Solution {
public:
    int sum[101][101]; 
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int n = matrix.size(), m = matrix[0].size();
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
        int res = INT_MIN;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int p = i; p <= n; p++) {
                    for (int q = j; q <= m; q++) {
                        int cur = sum[p][q] - sum[p][j-1] - sum[i-1][q] + sum[i-1][j-1];
                        if (cur <= k)
                            res = max(cur, res);    
                    }
                }
            }
        }
        return res;
    }
};

前缀和+二分

类似两数之和，如果知道一个数，求另外一个数，可以放到某个数据结构中进行查询。

同样，前缀和是递增的，可以根据递增特性确定上、下、右边界，去查找左边界，如果矩阵中有负数，便不可以进行二分搜索。

class Solution {
public:
    int sum[101][101]; 
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int n = matrix.size(), m = matrix[0].size();
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
        int res = INT_MIN;
        for (int i = 1; i <= n; i++) {  // 上
            for (int j = i; j <= n; j++) { // 下
                set<int> st{0};
                for (int r = 1; r <= m; r++) { // 右
                    // 右边界与最左侧所围成的矩阵
                    int right = sum[j][r] - sum[i-1][r];
                    auto left = st.lower_bound(right - k);
                    if (left != st.end()) {
                        res = max(res, right - *left);
                    }
                    st.insert(right);
                }
            }
        }
        return res;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-04-22，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构