class048 二维前缀和、二维差分、离散化技巧

二维前缀和

  • 目的：生成一个结构，以后查询二维数组任何范围上的累加和都是O(1)的操作

  • 做法：生成二维前缀和数组sum,sum[i][i]代表从（0.0）~ (i,j)范围内所有数值的和

  • 自己等于自己左边数+自己上边数-自己左上数+自己

  • 注意：实际操作中往往补第0行，第0列来简化判断，例如原来的第数组0行第0列的值既没有左数，上数，也没有左上数

    1
    sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];

  • 要求：查询 从（a,b）~ (c,d)范围内数字的累加和

    1
    num = sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1];

    题目：304. 二维区域和检索 - 矩阵不可变

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
class NumMatrix {
    public int[][] sum;
    public NumMatrix(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        sum = new int[n+1][m+1];
        for(int a = 1,c = 0; a <= n;a++,c++){
            for(int b = 1,d = 0;b <= m;b++,d++){
                sum[a][b] = matrix[c][d];
            }
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int a, int b, int c, int d) {
        a++;
        b++;
        c++;
        d++;
        return sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1];
    }
}

题目：1139. 最大的以 1 为边界的正方形

  • 做法：构建二维前缀和数组，从（0，0）一直遍历到（n-1，m-1），时间复杂度为O(n*m * min(n,m)),判断一个正方形边界全为1，只需判断外边正方形数字的累加和减去里面正方形数字的累加和是否等于周长
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
class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        //构建前缀和数组
        build(grid,n,m);
        //没有这种正方形
        if(sum(grid,0,0,n-1,m-1) == 0){
            return 0;
        }
        int ans = 1;
        for(int a = 0;a < n ;a++){
            for(int b = 0;b <m ;b++){
                for(int c = (ans+a),d = (ans + b) ,k = (ans+1);c < n && d < m;c++,d++,k++){
                    if(sum(grid,a,b,c,d) - sum(grid,a+1,b+1,c-1,d-1) == (k-1) << 2){
                        ans = k;
                    }
                }
            }
        }
        return ans*ans;
    }
    public static void build(int[][] grid ,int n ,int m){
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                grid[i][j] += get(grid,i,j-1) + get(grid,i-1,j) - get(grid,i-1,j-1);
            }
        }
    }
    public static int get(int[][]grid, int i ,int j){
        //本题并未采用添加0行0列的做法，使空间复杂度为O(1),所以要判断越界的情况
        return (i < 0 || j <0) ? 0 :grid[i][j];
    }
    public static int sum(int[][] grid, int a,int b,int c,int d){
        //原数组为2*2的情况
        return a > c ? 0 : grid[c][d] - get(grid,c,b-1) - get(grid,a-1,d) + get(grid,a-1,b-1);
    }
}

二维差分

  • 在二维数组中，如果经历如下的过程

    批量的做如下的操作，每个操作都有独立的a、b、c、d、v

    void add(a, b, c, d, v) : 左上角(a,b)到右下角(c,d)范围上，每个数字+v，怎么快速处理？

  • 通过下述的add方法和build方法实现（往往在真实数据周围围上一圈0来方便运算，数组长宽都加2）

1
2
3
4
5
6
public static void add(int a,int b,int c,int d,int k ){
       diff[a][b] += k;
       diff[c+1][b] -= k;
       diff[a][d+1] -= k;
       diff[c+1][d+1] += k;
    }
1
2
3
4
5
6
7
public static void build(){
        for(int i = 1;i < diff.length;i ++){
            for(int j = 1;j < diff[0].length;j++){
                diff[i][j] += diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1]; 
            }
        }
    }

题目：2132. 用邮票贴满网格图

  • 循环遍历二维矩阵，检查以这个点开始，长为h,宽为m的区域的累加和是否为0，如果是，则这个位置可以贴邮票（区域全部加1）
  • 但是每个位置都可能被多个邮票贴过，所以不能在原数组修改，维护一个差分数组来完成贴邮票的操作
  • 为了能够快速得到区域累加和，维护一个前缀和数组
  • 最后如果原数组某个位置是0，而差分数组这个位置同样是0，说明这个位置没有贴上邮票（没有办法覆盖所有的空格），返回false
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
49
50
51
52
53
54
class Solution {
    public boolean possibleToStamp(int[][] grid, int h, int w) {
        int n = grid.length;
        int m = grid[0].length;
        //前缀和数组左侧和右侧用0包裹
        int[][] sum = new int[n+1][m+1];
        //差分数组周围用0包裹
        int[][] diff = new int[n+2][m+2];
        for(int i = 0 ;i < n;i++){
            for(int j = 0;j < m;j++){
                sum[i+1][j+1] = grid[i][j];
            }
        }
        build(sum);
        //遍历数组
        for(int a = 1,c = a + h -1 ;c <= n;a++,c++){
            for(int b = 1,d = b + w -1;d <= m;b++,d++){
                //区域累加和为0，整体加1
                if(sumRegion(sum,a,b,c,d) == 0){
                    add(diff,a,b,c,d);
                }
            }
        }
        build(diff);
        //检验
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                //数组中的某个位置是0，在差分数组中任然是0，说明0没有被完全覆盖
                if(grid[i][j] == 0 && diff[i+1][j+1] == 0){
                    return false;
                }
            }
        }
        return true;
    }
    public void build(int[][] sum){
        for(int i = 1;i < sum.length ;i++){
            for(int j = 1;j < sum[0].length;j++){
                sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]; 
            }
        }
    }
    //区域累加和
    public int sumRegion(int[][] sum,int a,int b,int c,int d){
        return sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1];
    }
    //差分
    public void add(int[][] sum,int a,int b,int c,int d){
        sum[a][b] += 1;
        sum[c+1][b] -= 1;
        sum[a][d+1] -= 1;
        sum[c+1][d+1] += 1;
    }
}

离散化技巧

题目：LCP 74. 最强祝福力场

  • 统计力场的四条边的坐标，由于会出现0.5，可将坐标乘以2
  • 由于坐标的值可能会非常大，无法维护那么大的差分数组，所以离散化横纵坐标，不管坐标原来的值有多大，只返回它在横坐标数组中的索引并加1
  • 二维差分和二维前缀和复原
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    public int fieldOfGreatestBlessing(int[][] fields) {
        int n = fields.length;
        //记录左侧最远和右侧最远
        long[] xs = new long[n << 1];
        //上侧和下侧
        long[] ys = new long[n << 1];
        for(int i = 0,k = 0,p = 0;i < n;i++){
            long x = fields[i][0];
            long y = fields[i][1];
            long r = fields[i][2];
            xs[k++] = (x << 1) - r;
            xs[k++] = (x << 1) + r;
            ys[p++] = (y << 1) - r;
            ys[p++] = (y << 1) + r;
        }
       int sizex = sort(xs);
       int sizey = sort(ys);
       int[][] diff = new int[sizex+2][sizey+2];
       for(int i = 0,a,b,c,d;i < n;i++){
            long x = fields[i][0];
            long y = fields[i][1];
            long r = fields[i][2];
            a = rank(xs,(x << 1) - r,sizex);
            b = rank(ys,(y << 1) - r,sizey);
            c = rank(xs,(x << 1) + r,sizex);
            d = rank(ys,(y << 1) + r,sizey);
            add(diff,a,b,c,d);
       }
       int ans = 1;
       for(int i = 1;i < diff.length;i++){
        for(int j = 1;j < diff[0].length;j++){
            diff[i][j] += diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1];
            ans = Math.max(diff[i][j],ans);
        }
       }
       return ans;
    }
    //返回除去重复值后的数组长度
    public static int sort(long[] arr){
        Arrays.sort(arr);
        int size = 1;
        for(int i = 1;i < arr.length;i++){
            if(arr[i] != arr[size - 1] ){
                arr[size++] = arr[i];
            }
        }
        return size;
    }
    //返回v在数组中的索引并加1
    public static int rank(long[] arr,long v,int size){
        int l = 0;
        int r = size - 1;
        int ans = 0;
        while(l <= r){
            int m = (r - l) / 2 + l;
            if(arr[m] >= v){
                r = m - 1;
                ans = m;
            }else{
                l = m + 1;
            }
        }
        return ans + 1;
    }
    public static void add(int[][] diff,int a,int b,int c,int d){
        diff[a][b] += 1;
        diff[c+1][b] -= 1;
        diff[a][d+1] -= 1;
        diff[c+1][d+1] += 1;
    }
}