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

Categories:

题目描述
思路分析
1. 解法一：枚举上下边界 + 前缀和 + 有序集合（推荐）
相似题目

题目描述

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

思路分析

解法一：枚举上下边界 + 前缀和 + 有序集合（推荐）

核心思路：

枚举矩形上边界 r1 和下边界 r2，将两行之间每一列的元素累加压缩成一维数组 colSum

问题转化为：在一维数组 colSum 中，找最大子数组和不超过 K

利用前缀和：sum[r] - sum[l] <= K 等价于 sum[l] >= sum[r] - K，即在已有前缀和中找最小的 >= sum[r] - K 的值

用 TreeSet（Java）/ sortedcontainer（Go 用有序集合模拟）维护前缀和，支持 O(log n) 查找

复杂度分析：

时间复杂度：O(m² · n · log n)，其中 m 表示行数，n 表示列数，枚举上下边界 O(m²)，每行前缀和查询 O(n log n)

空间复杂度：O(n)，存储列累加和与前缀和集合

import java.util.TreeSet;

class Solution {

  public int maxSumSubmatrix(int[][] matrix, int k) {
    int m = matrix.length;
    int n = matrix[0].length;
    int result = Integer.MIN_VALUE;

    // 枚举上边界行
    for (int r1 = 0; r1 < m; r1++) {
      int[] colSum = new int[n];

      // 枚举下边界行
      for (int r2 = r1; r2 < m; r2++) {
        // 将当前行累加到列和中
        for (int c = 0; c < n; c++) {
          colSum[c] += matrix[r2][c];
        }

        // 在一维数组 colSum 中，找最大子数组和不超过 K
        TreeSet<Integer> prefixSet = new TreeSet<>();
        prefixSet.add(0);
        int prefixSum = 0;

        for (int c = 0; c < n; c++) {
          prefixSum += colSum[c];

          // 找最小的 prefixSet 中 >= prefixSum - k 的值
          Integer lower = prefixSet.ceiling(prefixSum - k);
          if (lower != null) {
            result = Math.max(result, prefixSum - lower);
          }

          prefixSet.add(prefixSum);
        }
      }
    }

    return result;
  }
}

import "math"

// 使用有序集合模拟（基于红黑树的 treap 实现）
// 简化版：使用排序切片 + 二分查找
func maxSumSubmatrix(matrix [][]int, k int) int {
    m, n := len(matrix), len(matrix[0])
    result := math.MinInt32

    // 枚举上边界行
    for r1 := 0; r1 < m; r1++ {
        colSum := make([]int, n)

        // 枚举下边界行
        for r2 := r1; r2 < m; r2++ {
            // 累加当前行到列和
            for c := 0; c < n; c++ {
                colSum[c] += matrix[r2][c]
            }

            // 在一维 colSum 中找最大子数组和不超过 k
            result = max363(result, maxSumNoLargerThanK(colSum, k))
        }
    }

    return result
}

// 在数组中找最大子数组和不超过 k，使用有序切片 + 二分
func maxSumNoLargerThanK(arr []int, k int) int {
    result := math.MinInt32
    prefixSet := []int{0}
    prefixSum := 0

    for _, v := range arr {
        prefixSum += v

        // 二分查找最小的 >= prefixSum - k 的前缀和
        target := prefixSum - k
        lo, hi := 0, len(prefixSet)
        for lo < hi {
            mid := (lo + hi) / 2
            if prefixSet[mid] < target {
                lo = mid + 1
            } else {
                hi = mid
            }
        }

        if lo < len(prefixSet) {
            if val := prefixSum - prefixSet[lo]; val > result {
                result = val
            }
        }

        // 将 prefixSum 插入有序切片
        pos := lo
        lo2, hi2 := 0, len(prefixSet)
        for lo2 < hi2 {
            mid := (lo2 + hi2) / 2
            if prefixSet[mid] <= prefixSum {
                lo2 = mid + 1
            } else {
                hi2 = mid
            }
        }
        pos = lo2
        prefixSet = append(prefixSet, 0)
        copy(prefixSet[pos+1:], prefixSet[pos:])
        prefixSet[pos] = prefixSum
    }

    return result
}

func max363(a, b int) int {
    if a > b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
53. 最大子数组和	中等	动态规划、前缀和
304. 二维区域和检索 - 矩阵不可变	中等	前缀和、矩阵
862. 和至少为 K 的最短子数组	困难	前缀和、单调队列
560. 和为 K 的子数组	中等	前缀和、哈希表
930. 和相同的二元子数组	中等	前缀和、滑动窗口
1074. 元素和为目标值的子矩阵数量	困难	前缀和、哈希表、矩阵

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/78894788