使用 oh-my-zsh

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

给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。

示例:

输入: matrix = [[1,0,1],[0,-2,3]], k = 2
输出: 2 
解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

说明：

• 矩阵内的矩形区域面积必须大于 0。
• 如果行数远大于列数，你将如何解答呢？

题解

1、最大前缀和的二维形式

• 求每一行的前缀和

• 穷举所有矩形，求其和

  • 更新最大值
  • 若求的的值等于k, 直接返回

• 代码

// c++
class Solution {
public:
    // n行数，m列数
    // O(m^2 * nlog(n)) 对所有可能的左右边界，在前缀和的基础上求小于k的最大连续子数组和
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int n = matrix.size(), m = matrix[0].size();
        // 预处理前缀和，求每一行的前缀和
        vector<vector<int>> v(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                v[i][j] = v[i][j - 1] + matrix[i - 1][j - 1];
            }
        }

        // 两个for遍历所有可能的左右边界
        int res = INT_MIN;
        // 对于每一列
        for (int l = 1; l <= m; l++) {
            // 从第l列开始，遍历剩余的列
            for (int r = l; r <= m; r++) {
                // 存set，set查询lower_bound O(log(n))
                set<int> st;
                st.insert(0);
                int cur = 0;
                // 对于每一行，求可能的矩阵
                for (int i = 1; i <= n; i++) {
                    // 第i-1行中l-r直接的数之和
                    int now = v[i][r] - v[i][l - 1];
                    cur += now;
                    // 对于当前的前缀和，找数中大于等于cur-k的最小元素
                    // 设找到的数为p，则p大于等于cur-k，必有 cur - p <= k
                    // 所有最小的p，使得cur-p的值最大，且该值小于等于k

                    // lower_bound()返回值是一个迭代器,返回指向大于等于key的第一个值的位置
                    auto it = st.lower_bound(cur - k);
                    // 更新最大值
                    if (it != st.end()) res = max(res, cur - *it);
                    st.insert(cur);
                    // 找到最大值，提前结束
                    if (res == k) return res;
                }
            }
        }

        return res;
    }
};

// 作者：zhenying
// 链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/cpp-86-qian-zhui-he-chu-li-by-zhenying/

• 16ms

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        if (n == 0) return 0;
        int m = matrix[0].size();
        if (m == 0) return 0;
        int res = INT_MIN;
        // 对于所有的列
        for (int s = 0; s < m; ++s) {
            // 申请一个大小等于行数的数组
            vector<int> rowSum(n, 0);
            // 从第s列开始的所有列
            for (int e = s; e < m; ++e) {
                // 记录矩阵和
                int maxSum = 0;
                // 对于行求和
                for (int i = 0, acc = 0; i < n; ++i) {
                    rowSum[i] += matrix[i][e];
                    acc += rowSum[i];// 累加
                    // 这个表达式有点意思
                    acc <= k && res < acc ? res = acc : 0;
                    acc < 0 ? acc = 0 : maxSum = max(maxSum, acc);
                }
                // 找到最大解，提前结束
                if (res == k) return k;
                // 否则继续循环，继续叠加
                if (maxSum < k) continue;
                // 集合
                set<int> hash{0};
                for (int i = 0, acc = 0; i < n; ++i) {
                    acc += rowSum[i];// 累加
                    // 求hash中第一个大于等于acc-k的下标
                    auto iter = hash.lower_bound(acc - k);
                    iter != hash.end() && res < acc - *iter ? res = acc - *iter : 0;
                    hash.insert(acc);
                }
                // 提前结束
                if (res == k) return k;
            }
        }
        return res;
    }
};

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com