lintcode 558 · 滑动窗口矩阵的最大值【二维数组前缀和 中等 vip】

题目

https://www.lintcode.com/problem/558/description

给一个 n * m 的一个矩阵, 以及一个移动的矩阵窗口 (大小为 k * k), 移动窗口从左上角到右下角, 找到每一次移动窗口得到的和中的最大值, 返回 0, 如果结果不存在


样例
样例 1:

输入：[[1,5,3],[3,2,1],[4,1,9]]，k=2
输出：13
解释：
最初窗口位于矩阵的起点如下
	[
	  [|1, 5|, 3],
	  [|3, 2|, 1],
	  [4, 1, 9],
	]
,得到和为 11;

然后窗口向前移动一步
	[
	  [1, |5, 3|],
	  [3, |2, 1|],
	  [4, 1, 9],
	]
,得到和为 11;

然后窗口继续移动一步
	[
	  [1, 5, 3],
	  [|3, 2|, 1],
	  [|4, 1|, 9],
	]
,得到和为 10;

然后窗口继续移动一步
	[
	  [1, 5, 3],
	  [3, |2, 1|],
	  [4, |1, 9|],
	]
,得到和为 13;
所以最终，从所有窗口中得到最大值为13。
样例 2:

输入：[[10]，k=1
输出：10
解释：
滑动窗口的大小为 1*1，返回 10。
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

前置知识

  二维数组前缀和公式： 
	presum[i][j] = 
	matrix[i - 1][j - 1] 
	+ presum[i - 1][j] 
	 + presum[i][j - 1] 
	 - presum[i - 1][j - 1];
1
2
3
4
5
6

答案

public class Solution {
    /**
     * @param matrix: an integer array of n * m matrix
     * @param k: An integer
     * @return: the maximum number
     */
    public int maxSlidingMatrix(int[][] matrix, int k) {
     //二维数组前缀和
        if (matrix == null || matrix[0].length == 0) return -1;
        int n = matrix.length, m = matrix[0].length;
        if (n < k || m < k) return 0;

        int[][] presum = new int[n + 1][m + 1];


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

        int ans = Integer.MIN_VALUE;
        for (int i = k; i <= n; i++) {
            for (int j = k; j <= m; j++) {
                int diff = presum[i][j] + presum[i - k][j - k];

                diff -= presum[i - k][j];
                diff -= presum[i][j - k];

                ans = Math.max(ans, diff);

            }
        }

        return ans;
    }
}
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