题目描述

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

样例

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

提示

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

算法

(暴力枚举 + 前缀和 + 二分) $O(n^2m \log m)$

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

时间复杂度

• 列区间共有 $O(n^2)$ 个，每个一维问题解决时间为 $O(m \log m)$。
• 故总时间复杂度为 $O(n^2m \log m)$。

空间复杂度

• 需要额外 $O(m)$ 的空间记录在当前列区间下，每一行的和。

C++ 代码

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        int ans = INT_MIN;

        for (int lo = 0; lo < n; lo++) {
            vector<int> row(m, 0);
            for (int hi = lo; hi < n; hi++) {
                set<int> pre;
                int sum = 0;

                pre.insert(0);
                for (int i = 0; i < m; i++) {
                    row[i] += matrix[i][hi];
                    sum += row[i];
                    auto it = pre.lower_bound(sum - k);
                    if (it != pre.end())
                        ans = max(ans, sum - *it);
                    pre.insert(sum);
                }
            }
        }

        return ans;
    }
};