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

链接：363.矩形区域不超过K的最大数值和
难度：Hard
标签：数组、二分查找、矩阵、有序集合、前缀和
简介：给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题解 1 - typescript

• 编辑时间：2021-04-22
• 执行用时：408ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：暴力循环四次。

function maxSumSubmatrix(matrix: number[][], k: number): number {
  const rowLen = matrix.length;
  const colLen = matrix[0].length;
  const dp: number[][] = new Array(rowLen + 1).fill(0).map(_ => new Array(colLen + 1).fill(0));
  let max = -Infinity;
  for (let row = 0; row < rowLen; row++) {
    for (let col = 0; col < colLen; col++) {
      let num = matrix[row][col] + dp[row + 1][col] + dp[row][col + 1] - dp[row][col];
      if (num === k) return k;
      dp[row + 1][col + 1] = matrix[row][col] + dp[row + 1][col] + dp[row][col + 1] - dp[row][col];
      for (let i = 0; i <= row; i++) {
        for (let j = 0; j <= col; j++) {
          const areaNum = num - dp[i][col + 1] - dp[row + 1][j] + dp[i][j];
          if (areaNum === k) return k;
          else if (areaNum < k) max = Math.max(max, areaNum);
        }
      }
    }
  }
  return max;
}