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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

示例 1： e1(1).png

输入：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(int[][] mat, int threshold) {
        /*
         * 涉及知识点 ： 1、 前缀和  2、 容斥原理
         *              容斥原理：
         *                  正方形面积 = 已求出的矩形面积运算得出

         *                  sum[i][j] = mat[i][j] + sum[i - 1][j] + 
         *                              sum[i][j - 1] - sum[i - 1][j - 1]

         *                  1  1  1      1  1     1  1  1       1  1
         *                  1  1  1    = 1  1  +  1  1  1   -   1  1  +       
         *                  1  1  1      1  1                             1

         *                  ->  9 = 6 + 6 - 4 + 1
         *              前缀和：
         *                  计算所有位置面积以方便求解过程中使用         
         */
        int m = mat.length;
        int n = mat[0].length;
        int res = 0;
        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] = mat[i - 1][j - 1] + sum[i][j - 1]
                            + sum[i - 1][j] - sum[i - 1][j - 1];
            }
        }

        // 根据所求出前缀和求解
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= i && k <= j; k++) {  
                    // 从边长为1开始扩展正方形大小
                    int ans = sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k];
                    if (ans > threshold) {
                        break;
                    }
                    res = Math.max(res, k);
                }
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

# 总结

分析出几种情况，然后分别对各个情况实现

#Java