欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-06 21:34:20
...

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

Example 3:

Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3

Example 4:

Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2

Constraints:

  • 1 <= m, n <= 300
  • m == mat.length
  • n == mat[i].length
  • 0 <= mat[i][j] <= 10000
  • 0 <= threshold <= 10^5

分析

题目的意思是:求出构成的正方形且小于阈值的最大正方形,这道题目我也不会,看懂了也不会做,后面发现可以先用dp数组把以当前位置结尾的最大正方形的和求出来,然后再一个一个的遍历找最大的正方形。求和的代码为:

dp[i][j]=mat[i-1][j-1]+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]

存放的是以i,j结尾的最大矩形的和。

res=dp[i][j]-dp[i][j-k]-dp[i-k][j]+dp[i-k][j-k]

res存放的是以k为边构成的矩形的和。

代码

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        m=len(mat)
        n=len(mat[0])
        least=min(m,n)
        dp=[[0]*(n+1) for i in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                dp[i][j]=mat[i-1][j-1]+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]
                
        res=0
        for k in range(least,-1,-1):
            for i in range(k,m+1):
                for j in range(k,n+1):
                    res=dp[i][j]-dp[i][j-k]-dp[i-k][j]+dp[i-k][j-k]
                    if(res<=threshold):
                        return k
        return 0

参考文献

[LeetCode] C++ DP solution with comments and example