1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold¶
题目信息¶
- 题号:
1292
- 难度:
Medium
- 主题:
矩阵、二维前缀和、二分查找
- 原题:
- 重点:
寻找元素和不超过
threshold的连续正方形子矩阵,并最大化边长;不存在合法正方形时返回0
题目重述¶
给定非负整数矩阵 mat 和整数 threshold。一个正方形子矩阵必须由连续行和连续列组成。
请返回元素总和不超过 threshold 的正方形子矩阵能够达到的最大边长。若连边长为 1 的正方形都不存在,返回 0。
1 <= mat.length, mat[i].length <= 300,0 <= mat[i][j] <= 10^4,0 <= threshold <= 10^5。
自建示例¶
多个单位元素可以组成更大的合法正方形:
输入:mat = [[1,1,1],[1,1,1]], threshold = 4
输出:2
解释:任意 2 x 2 子矩阵的元素和为 4;矩阵高度不足以形成边长 3 的正方形。
阈值小于所有单格元素时返回零:
输入:mat = [[2,3]], threshold = 1
输出:0
解释:任意 1 x 1 子矩阵的元素和都超过阈值。