Leetcode - Maximum Side Length of a Square with Sum Less than or Equal to Threshold

violet posted @ May 05, 2020 06:43:06 AM in 算法 with tags Algorithm Golang PrefixSum , 262 阅读

https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/

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.

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

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