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

Categories:

题目描述
思路分析
1. 解法一：二维前缀和 + 二分（推荐）
相似题目

题目描述

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

思路分析

解法一：二维前缀和 + 二分（推荐）

核心思路：

构建二维前缀和 sum，可 O(1) 查询任意子矩形和。

对边长 len 进行二分，检查是否存在和不超过 threshold 的正方形。

若存在则扩展边长，否则缩小。

复杂度分析：

时间复杂度：O(mn log K)，其中 K 为最小边长。

空间复杂度：O(mn)，存储前缀和。

class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        int left = 0;
        int right = Math.min(m, n);
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (exists(sum, m, n, mid, threshold)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean exists(int[][] sum, int m, int n, int len, int threshold) {
        for (int i = len; i <= m; i++) {
            for (int j = len; j <= n; j++) {
                int total = sum[i][j] - sum[i - len][j] - sum[i][j - len] + sum[i - len][j - len];
                if (total <= threshold) {
                    return true;
                }
            }
        }
        return false;
    }
}

func maxSideLength(mat [][]int, threshold int) int {
    m := len(mat)
    n := len(mat[0])
    sum := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        sum[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mat[i-1][j-1]
        }
    }

    left, right := 0, min(m, n)
    for left < right {
        mid := left + (right-left+1)/2
        if existsSquare(sum, m, n, mid, threshold) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

func existsSquare(sum [][]int, m, n, length, threshold int) bool {
    for i := length; i <= m; i++ {
        for j := length; j <= n; j++ {
            total := sum[i][j] - sum[i-length][j] - sum[i][j-length] + sum[i-length][j-length]
            if total <= threshold {
                return true
            }
        }
    }
    return false
}

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

相似题目

题目	难度	考察点
304. 二维区域和检索 - 矩阵不可变	中等	前缀和
1314. 矩阵区域和	中等	前缀和
1277. 统计全为 1 的正方形子矩阵	中等	DP
221. 最大正方形	中等	DP
363. 矩形区域不超过 K 的最大数值和	困难	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/50684234