Question

1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

中文文档

Description

Given a m x n matrix mat and an integer threshold, return _the maximum side-length of a square with a sum less than or equal to _threshold_ or return _0_ if there is no such square_.

 

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: 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
Output: 0

 

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 300
• 0 <= mat[i][j] <= 104
• 0 <= threshold <= 105

Solutions

Solution 1

class Solution:
  def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
    def check(k: int) -> bool:
      for i in range(m - k + 1):
        for j in range(n - k + 1):
          v = s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j]
          if v <= threshold:
            return True
      return False

    m, n = len(mat), len(mat[0])
    s = [[0] * (n + 1) for _ in range(m + 1)]
    for i, row in enumerate(mat, 1):
      for j, x in enumerate(row, 1):
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x
    l, r = 0, min(m, n)
    while l < r:
      mid = (l + r + 1) >> 1
      if check(mid):
        l = mid
      else:
        r = mid - 1
    return l

class Solution {
  private int m;
  private int n;
  private int threshold;
  private int[][] s;

  public int maxSideLength(int[][] mat, int threshold) {
    m = mat.length;
    n = mat[0].length;
    this.threshold = threshold;
    s = new int[m + 1][n + 1];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
      }
    }
    int l = 0, r = Math.min(m, n);
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }

  private boolean check(int k) {
    for (int i = 0; i < m - k + 1; ++i) {
      for (int j = 0; j < n - k + 1; ++j) {
        if (s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] <= threshold) {
          return true;
        }
      }
    }
    return false;
  }
}

class Solution {
public:
  int maxSideLength(vector<vector<int>>& mat, int threshold) {
    int m = mat.size(), n = mat[0].size();
    int s[m + 1][n + 1];
    memset(s, 0, sizeof(s));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
      }
    }
    auto check = [&](int k) {
      for (int i = 0; i < m - k + 1; ++i) {
        for (int j = 0; j < n - k + 1; ++j) {
          if (s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] <= threshold) {
            return true;
          }
        }
      }
      return false;
    };
    int l = 0, r = min(m, n);
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
};

func maxSideLength(mat [][]int, threshold int) int {
  m, n := len(mat), len(mat[0])
  s := make([][]int, m+1)
  for i := range s {
    s[i] = make([]int, n+1)
  }
  for i := 1; i <= m; i++ {
    for j := 1; j <= n; j++ {
      s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1]
    }
  }
  check := func(k int) bool {
    for i := 0; i < m-k+1; i++ {
      for j := 0; j < n-k+1; j++ {
        if s[i+k][j+k]-s[i][j+k]-s[i+k][j]+s[i][j] <= threshold {
          return true
        }
      }
    }
    return false
  }
  l, r := 0, min(m, n)
  for l < r {
    mid := (l + r + 1) >> 1
    if check(mid) {
      l = mid
    } else {
      r = mid - 1
    }
  }
  return l
}

function maxSideLength(mat: number[][], threshold: number): number {
  const m = mat.length;
  const n = mat[0].length;
  const s: number[][] = Array(m + 1)
    .fill(0)
    .map(() => Array(n + 1).fill(0));
  for (let i = 1; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
    }
  }
  const check = (k: number): boolean => {
    for (let i = 0; i < m - k + 1; ++i) {
      for (let j = 0; j < n - k + 1; ++j) {
        if (s[i + k][j + k] - s[i + k][j] - s[i][j + k] + s[i][j] <= threshold) {
          return true;
        }
      }
    }
    return false;
  };

  let l = 0;
  let r = Math.min(m, n);
  while (l < r) {
    const mid = (l + r + 1) >> 1;
    if (check(mid)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  return l;
}