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

难度: 🌕🌕

问题描述

---

解法 1

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        // 思路：
        // 1. 如果为 一维数组，求 [i, j] 使得 sum[i, j] <= k 如何求？
        // 1) 求出 一维数组的前缀和数组 sum[]， 两层遍历找到 diff <= k 的 max
        // 2) 暴搜 - 直接两层遍历，固定 i，求 [i, j] 的和，找到满足条件的 max
        // 3) 如何优化？
        //    先一次遍历，找到一维数组中的最大区间和 sum，判断与 k 的关系
        //    若 sum <= k，说明满足条件的最大值就是 sum，无需二层循环
        //    若 sum > k，则需要二层遍历找到比 k 小的区间和
        // 4) 以上无论怎么计算，平均复杂度均为 O(N * N)，最优复杂度为 O(N)
        // 5) 再如何进行优化？
        //    那么只能考虑如何降低复杂度为 O(NlogN)?
        //    已知前缀和数组 sum[]，在 j 时使得 sum[j] - sum[?] <= k ==> sum[?] >= sum[j] - k ==> TreeSet.ceiling() 函数

        // 2. 当前为 二维数组，求 [i, j] --> [m, n] 的和 <= k 的 max 如何求？
        // 1) 暴搜 - 四层遍历，分别固定 i, j, m 让 n 变化，计算 矩形区域和，复杂度 O(m * n * m * n)
        // 2) 如何优化？
        // ① 平均复杂度不变，通过 一维数组 记录左边界 i 到右边界 j 的区间和 sum[]，然后在 一维数组 sum[] 中采用 1.3) 计算结果
        // ② 仍然将为一维数组计算，然后通过 1.5) 降低复杂度为 O(n * n * mlogm) --> 针对固定左右两列，若固定上下两行，则相反
        int m = matrix.length;
        int n = matrix[0].length;
        int res = k + 1;

        for(int i = 0; i < n; i ++) {
            // i 为左边界
            int[] sum = new int[m];
            for(int j = i; j < n; j ++) {
                // j 为右边界
                // 求 [i, j] 列之间的 sum[] 行，左边界固定，每次右移右边界都在之前 sum[] 的基础上 +
                for(int p = 0; p < m; p ++) {
                    sum[p] += matrix[p][j];
                }
                // 得到一维数组 sum[] 后找到当前轮满足条件的最优结果
                int tmp = mySol(sum, k);
                // System.out.println(i + ":" + j  + "  " + Arrays.toString(sum) + "  " + tmp);
                if(tmp == k) {
                    return k;
                }
                if(res > k) {
                    res = tmp;
                    continue;
                }
                // res < k
                if(tmp < k && tmp > res) {
                    res = tmp;
                }
            }
        }
        return res;
    }

    private int mySol(int[] arr, int k) {
        int len = arr.length;
        int[] dp = new int[len];
        dp[0] = arr[0];

        int max = arr[0];

        for(int i = 1; i < len; i ++) {
            dp[i] = Math.max(dp[i - 1], 0) + arr[i];
            max = Math.max(max, dp[i]);
        }
        if(max <= k) {
            return max;
        }

        // max > k
        int res = k + 1;
        for(int i = 0; i < len; i ++) {
            int sum = 0;
            for(int j = i; j < len; j ++) {
                sum += arr[j];
                if(res > k) {
                    res = sum;
                    continue;
                }
                if(sum == k) {
                    return k;
                } else if(sum < k && sum > res) {
                    res = sum; // sum 比原来的 res 更满足要求
                }
            }
        }
        return res;
    }
}

---

输出 1

---

解法 2 - 借助 TreeSet

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        // 思路：
        // 1. 如果为 一维数组，求 [i, j] 使得 sum[i, j] <= k 如何求？
        // 1) 求出 一维数组的前缀和数组 sum[]， 两层遍历找到 diff <= k 的 max
        // 2) 暴搜 - 直接两层遍历，固定 i，求 [i, j] 的和，找到满足条件的 max
        // 3) 如何优化？
        //    先一次遍历，找到一维数组中的最大区间和 sum，判断与 k 的关系
        //    若 sum <= k，说明满足条件的最大值就是 sum，无需二层循环
        //    若 sum > k，则需要二层遍历找到比 k 小的区间和
        // 4) 以上无论怎么计算，平均复杂度均为 O(N * N)，最优复杂度为 O(N)
        // 5) 再如何进行优化？
        //    那么只能考虑如何降低复杂度为 O(NlogN)?
        //    已知前缀和数组 sum[]，在 j 时使得 sum[j] - sum[?] <= k ==> sum[?] >= sum[j] - k ==> TreeSet.ceiling() 函数

        // 2. 当前为 二维数组，求 [i, j] --> [m, n] 的和 <= k 的 max 如何求？
        // 1) 暴搜 - 四层遍历，分别固定 i, j, m 让 n 变化，计算 矩形区域和，复杂度 O(m * n * m * n)
        // 2) 如何优化？
        // ① 平均复杂度不变，通过 一维数组 记录左边界 i 到右边界 j 的区间和 sum[]，然后在 一维数组 sum[] 中采用 1.3) 计算结果
        // ② 仍然将为一维数组计算，然后通过 1.5) 降低复杂度为 O(n * n * mlogm) --> 针对固定左右两列，若固定上下两行，则相反
        int m = matrix.length;
        int n = matrix[0].length;
        int res = k + 1;

        for(int i = 0; i < n; i ++) {
            // i 为左边界
            int[] sum = new int[m];
            for(int j = i; j < n; j ++) {
                // j 为右边界
                // 求 [i, j] 列之间的 sum[] 行，左边界固定，每次右移右边界都在之前 sum[] 的基础上 +
                // 边求 sum[p] 边计算 [0, p] 的前缀和
                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                int prev = 0;
                for(int p = 0; p < m; p ++) {
                    sum[p] += matrix[p][j];
                    prev += sum[p];
                    // 计算一个前缀和，找 ceiling()
                    Integer tmp = set.ceiling(prev - k);
                    if(tmp != null) {
                        // 说明存在 prev - tmp <= k
                        if(prev - tmp == k) {
                            return k;
                        }
                        if(res > k) {
                            res = prev - tmp;
                            continue;
                        }
                        if(prev - tmp > res) {
                            res = prev - tmp;
                        }
                    }
                    set.add(prev);
                }
            }
        }
        return res;
    }
}

---

输出 2