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

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

示例 1：

输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2

解释：

蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

示例 2：

输入：matrix = [[2,2,-1]], k = 3
输出：3

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-10⁵ <= k <= 10⁵

进阶：

如果行数远大于列数，该如何设计解决方案？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-sum-of-rectangle-no-larger-than-k

方法一：有序集合

C++提交内容：

class Solution {
public:int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {int ans = INT_MIN;int m = matrix.size(), n = matrix[0].size();for (int i = 0; i < m; ++i) { // 枚举上边界vector<int> sum(n);for (int j = i; j < m; ++j) { // 枚举下边界for (int c = 0; c < n; ++c) {sum[c] += matrix[j][c]; // 更新每列的元素和}set<int> sumSet{0};int s = 0;for (int v : sum) {s += v;auto lb = sumSet.lower_bound(s - k);if (lb != sumSet.end()) {ans = max(ans, s - *lb);}sumSet.insert(s);}}}return ans;}
};