Leetcode 363. 矩形区域不超过 K 的最大数值和（DAY 191）

旧城等待， 2022-09-16 08:50 55阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解 n^4超高时间复杂度）
     *  代码实现（首刷优化 好题）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解 n^4超高时间复杂度） ##

--------------------

class Solution { 
    public:
        int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { 
            int ret = INT_MIN;
            vector<vector<int>> row_cal(matrix.size(),vector<int>(matrix[0].size(),0));
            for(int i=0;i<matrix.size();++i)
                for(int j=0;j<matrix[0].size();++j)
                    row_cal[i][j] = matrix[i][j] + ((j) ? row_cal[i][j-1] : 0);
            
            for(int left=0;left<matrix[0].size();++left)
            { 
                for(int right=left;right<matrix[0].size();++right)
                { 
                    for(int up=0;up<matrix.size();++up)
                    { 
                        int tmp = 0;
                        for(int down=up;down<matrix.size();++down)
                        { 
                            tmp += (row_cal[down][right] - ((left) ? row_cal[down][left-1] : 0));
                            if(tmp <= k) ret = max(ret,tmp);
                        }
                    }
                }
            }
            return ret;
        }
    };

--------------------

## 代码实现（首刷优化 好题） ##

--------------------

class Solution { 
    public:
        int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { 
            int ret = INT_MIN;
            vector<vector<int>> row_cal(matrix.size(),vector<int>(matrix[0].size(),0));
            for(int i=0;i<matrix.size();++i)
                for(int j=1;j<matrix[0].size();++j)
                    matrix[i][j] += (matrix[i][j-1]);
            
            for(int left=0;left<matrix[0].size();++left)
            { 
                for(int right=left;right<matrix[0].size();++right)
                { 
                    set<int> set{ 0};
                    int sum = 0;
                    for(int pos=0;pos<matrix.size();++pos)
                    { 
                        sum += matrix[pos][right] - ((left) ? matrix[pos][left-1] : 0);
                        auto iter = set.lower_bound(sum-k);
                        if(iter != set.end())   ret = max(ret,sum-*iter);
                        set.emplace(sum); 
                    }
                }
            }
            return ret;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/964c51c0166d4c04bbd4e9c25286633a.png