LeetCode 矩阵区域不超过K的最大数值

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

示例:

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

说明：
矩阵内的矩形区域面积必须大于 0。
如果行数远大于列数，你将如何解答呢？
方法一：暴搜法。穷举所有的子矩阵。请先翻阅 LeetCode 二维区域和检索

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        vector<vector<int>> matrixSum;//matrixSum[row][col] 表示第[0,row]行[0,col]的和
        int rowSize = matrix.size();
        int colSize = matrix[0].size();
        for (auto nums : matrix) {
            //逐行记性求和、复制
            vector<int> rowSum;
            int tempSum = 0;
            for (auto num : nums) {
                tempSum += num;
                rowSum.push_back(tempSum);
            }
            matrixSum.push_back(rowSum);
        }
        //再同col下，对[0, row]进行求和
        for (int col = 0; col < colSize; ++col) {
            for (int row = 1; row < rowSize; ++row) {
                matrixSum[row][col] += matrixSum[row - 1][col];
            }
        }
        int result = INT_MIN;
        //四层循环穷举子矩阵（请先翻阅上面的链接，下面的算法都是上一题的）
        for (int row1 = 0; row1 < rowSize; ++row1){
            for (int col1 = 0; col1 < colSize; ++col1){
                for (int row2 = row1; row2 < rowSize; ++row2){
                    for (int col2 = col1; col2 < colSize; ++col2){
                        int tempRes;
                        if (row1 == 0 && col1 == 0) {
                            tempRes = matrixSum[row2][col2];
                        }
                        else if (row1 == 0) {
                            tempRes = matrixSum[row2][col2] - matrixSum[row2][col1 - 1];
                        }
                        else if (col1 == 0) {
                            tempRes =  matrixSum[row2][col2] - matrixSum[row1 - 1][col2];
                        }
                        else {
                            tempRes =  matrixSum[row2][col2] - matrixSum[row2][col1 - 1] - matrixSum[row1 - 1][col2] + matrixSum[row1 - 1][col1 - 1];
                        }
                        if (tempRes == k){
                            return tempRes;
                        }
                        else if (tempRes < k){
                            result = max(result, tempRes);
                        }
                    }
                }
            }
        }
        return result;
    }
};

LeetCode 矩阵区域不超过K的最大数值
网上的大佬代码，12ms示范代码。

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int row = matrix.size(), col = matrix[0].size();
        int ans =INT_MIN;
        for(int i = 0; i < col; i++)
        {
            vector<int> sum(row, 0);
            for(int j =i; j < col; j++)
            {
                set<int> st{0};
                int curSum =0, curMax = INT_MIN;
                for(int x = 0; x < row; x++)
                {
                    sum[x] += matrix[x][j];
                    curSum += sum[x];
                    auto it = st.lower_bound(curSum-k);
                    if(it!=st.end()) curMax = max(curSum - *it, curMax);
                    st.insert(curSum);
                }
                ans = max(curMax, ans);
            }
        }
        return ans;
    }
};

但是一行注释都没有。。。我发现好多优秀、高效的代码大都没有注释，我想问问写这种代码的大神，你们写出来只是给自己看的吗？如果是给自己看的，为啥要分享出来呢？如果不是那你写出来又有多少意义呢，有多少人看的懂呢？希望也许只是我一个人笨吧。

LeetCode 矩阵区域不超过K的最大数值

相关推荐