题目

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

示例 1：输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 输出：2

解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。

示例 2：输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1 输出：0

示例 3：输入：mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6 输出：3

示例 4：输入：mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184 输出：2

提示：1 <= m, n <= 300

m == mat.length

n == mat[i].length

0 <= mat[i][j] <= 10000

0 <= threshold <= 10^5

解题思路分析

1、前缀和+二分查找；时间复杂度O(n^2log(n))，空间复杂度O(n^2)

func maxSideLength(mat [][]int, threshold int) int {
   n, m := len(mat), len(mat[0])
   arr := make([][]int, n+1)
   for i := 0; i <= n; i++ {
      arr[i] = make([]int, m+1)
   }
   for i := 0; i < n; i++ {
      for j := 0; j < m; j++ {
         arr[i+1][j+1] = mat[i][j] + arr[i+1][j] + arr[i][j+1] - arr[i][j]
      }
   }
   res := min(n, m)
   left, right := 0, res // res可以为0
   for left <= right {
      mid := left + (right-left)/2
      if check(arr, mid, threshold) == true {
         left = mid + 1
         res = mid
      } else {
         right = mid - 1
      }
   }
   return res
}

func check(arr [][]int, mid int, threshold int) bool {
   for i := 1; i+mid <= len(arr); i++ {
      for j := 1; j+mid <= len(arr[i]); j++ {
         sum := arr[i+mid-1][j+mid-1] - arr[i+mid-1][j-1] - arr[i-1][j+mid-1] + arr[i-1][j-1]
         if sum <= threshold {
            return true
         }
      }
   }
   return false
}

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

2、前缀和；时间复杂度O(n^3)，空间复杂度O(n^2)

func maxSideLength(mat [][]int, threshold int) int {
   n, m := len(mat), len(mat[0])
   arr := make([][]int, n+1)
   for i := 0; i <= n; i++ {
      arr[i] = make([]int, m+1)
   }
   for i := 0; i < n; i++ {
      for j := 0; j < m; j++ {
         arr[i+1][j+1] = mat[i][j] + arr[i+1][j] + arr[i][j+1] - arr[i][j]
      }
   }
   res := 0
   for i := 1; i <= n; i++ {
      for j := 1; j <= m; j++ {
         for k := 0; i+k <= n && j+k <= m; k++ {
            value := arr[i+k][j+k] - arr[i-1][j+k] - arr[i+k][j-1] + arr[i-1][j-1]
            if value <= threshold && res < k+1 {
               res = k + 1
            }
            if value > threshold {
               break
            }
         }
      }
   }
   return res
}

3、前缀和；时间复杂度O(n^3)，空间复杂度O(n^2)

func maxSideLength(mat [][]int, threshold int) int {
   n, m := len(mat), len(mat[0])
   arr := make([][]int, n+1)
   for i := 0; i <= n; i++ {
      arr[i] = make([]int, m+1)
   }
   for i := 0; i < n; i++ {
      for j := 0; j < m; j++ {
         arr[i+1][j+1] = mat[i][j] + arr[i+1][j] + arr[i][j+1] - arr[i][j]
      }
   }
   res := 0
   for i := 1; i <= n; i++ {
      for j := 1; j <= m; j++ {
         for k := min(i, j); k > res; k-- {
            value := arr[i][j] - arr[i-k][j] - arr[i][j-k] + arr[i-k][j-k]
            if value <= threshold && res < k {
               res = k
               break
            }
         }
      }
   }
   return res
}

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

总结

Medium题目，二维前缀和问题