元素和小于等于阈值的正方形的最大边长

1292. 元素和小于等于阈值的正方形的最大边长

给你一个大小为 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

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 300
0 <= mat[i][j] <= 10⁴
0 <= threshold <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxSideLength(vector<vector<int>>& mat, int threshold) { } };

golang 解法, 执行用时: 68 ms, 内存消耗: 7.6 MB, 提交时间: 2023-06-08 11:12:45

func maxSideLength(mat [][]int, threshold int) int {
	m := len(mat)
	n := len(mat[0])
	sum := make([][]int, m+1)
	for i := range sum {
		sum[i] = make([]int, n+1)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			sum[i+1][j+1] = mat[i][j] + sum[i+1][j] + sum[i][j+1] - sum[i][j]
		}
	}
	maxlength := Min(m, n)
	l, r := 0, maxlength
	for l < r {
		mid := (l+r+1)/2
		if maxSideLengthHelper(sum, mid, threshold) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

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

func Min(args ...int) int {
	min := args[0]
	for _, item := range args {
		if item < min {
			min = item
		}
	}
	return min
}

javascript 解法, 执行用时: 88 ms, 内存消耗: 50 MB, 提交时间: 2023-06-08 11:12:05

/**
 * @param {number[][]} mat
 * @param {number} threshold
 * @return {number}
 */
var maxSideLength = function(mat, threshold) {
	if (!mat) return
	var rows = mat.length, columns = mat[0].length;
 	var dp = [];
    for (var r = 0; r <= rows; r++) {
        dp[r] = Array.apply(null, Array(columns+1)).map(function (i) {
            return 0;
        });
    }
    dp[1][1] = 1;
    // 二维前缀和矩阵
    for (let i=1; i<=rows; ++i) {
        for (let j=1; j<=columns; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1]
        }
    }
    // console.log('dp :>> ', dp);

    // 二维前缀和矩阵 子矩阵和 公式
    function getRect(x1, y1, x2, y2) {
        return dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
    }

    let edge = Math.min(mat.length, mat[0].length);
    let res = 0;
    for (let i=1; i<=rows; ++i) {
        for (let j=1; j<=columns; ++j) {
        // 循环枚举正方形边长
            for (let c=res+1; c<edge+1; c++) {
                if (i+c-1 <= rows && j+c-1 <= columns && getRect(i, j, i+c-1, j+c-1) <= threshold) {
                    res += 1
                } else {
                    break
                }
            }
        }
    }
    return res
};

/**
var mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]];
ret = maxSideLength(mat, 4);
console.log('ret :>> ', ret);
*/

python3 解法, 执行用时: 284 ms, 内存消耗: 22.8 MB, 提交时间: 2023-06-08 11:10:41

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        m, n = len(mat), len(mat[0])
        P = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]
        
        def getRect(x1, y1, x2, y2):
            return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]
        
        r, ans = min(m, n), 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                for c in range(ans + 1, r + 1):
                    if i + c - 1 <= m and j + c - 1 <= n and getRect(i, j, i + c - 1, j + c - 1) <= threshold:
                        ans += 1
                    else:
                        break
        return ans

cpp 解法, 执行用时: 84 ms, 内存消耗: 27.9 MB, 提交时间: 2023-06-08 11:10:25

class Solution {
public:
    int getRect(const vector<vector<int>>& P, int x1, int y1, int x2, int y2) {
        return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1];
    }

    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> P(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        int r = min(m, n), ans = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int c = ans + 1; c <= r; ++c) {
                    if (i + c - 1 <= m && j + c - 1 <= n && getRect(P, i, j, i + c - 1, j + c - 1) <= threshold) {
                        ++ans;
                    }
                    else {
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

cpp 解法, 执行用时: 116 ms, 内存消耗: 27.8 MB, 提交时间: 2023-06-08 11:09:49

class Solution {
public:
    int getRect(const vector<vector<int>>& P, int x1, int y1, int x2, int y2) {
        return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1];
    }

    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> P(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        int l = 1, r = min(m, n), ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            bool find = false;
            for (int i = 1; i <= m - mid + 1; ++i) {
                for (int j = 1; j <= n - mid + 1; ++j) {
                    if (getRect(P, i, j, i + mid - 1, j + mid - 1) <= threshold) {
                        find = true;
                    }
                }
            }
            if (find) {
                ans = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 492 ms, 内存消耗: 22.8 MB, 提交时间: 2023-06-08 11:09:20

# 二分法 + 前缀和
class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        m, n = len(mat), len(mat[0])
        P = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]
        
        def getRect(x1, y1, x2, y2):
            return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]
        
        l, r, ans = 1, min(m, n), 0
        while l <= r:
            mid = (l + r) // 2
            find = any(getRect(i, j, i + mid - 1, j + mid - 1) <= threshold for i in range(1, m - mid + 2) for j in range(1, n - mid + 2))
            if find:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans

上一题

下一题

详情