Sliding Window Matrix Maximum 558

Question

Given an array of n m matrix, and a moving matrix window (size k k), move the window from top left to botton right at each iteration, find the maximum sum of the elements inside the window at each moving. Return 0 if the answer does not exist.

Example

For matrix

[ [1, 5, 3], [3, 2, 1], [4, 1, 9], ]

The moving window size k = 2.

return 13.

At first the window is at the start of the array like this

[ [|1, 5|, 3], [|3, 2|, 1], [4, 1, 9], ]

,get the sum 11;

then the window move one step forward.

[ [1, |5, 3|], [3, |2, 1|], [4, 1, 9], ]

,get the sum 11;

then the window move one step forward again.

[ [1, 5, 3], [|3, 2|, 1], [|4, 1|, 9], ]

,get the sum 10;

then the window move one step forward again.

[ [1, 5, 3], [3, |2, 1|], [4, |1, 9|], ] ,get the sum 13;

SO finally, get the maximum from all the sum which is 13.

Challenge

O(n^2) time.

Solution

sum[i][j]表示0-i－1行和0-j－1列所有元素的和。

1. 建立sum矩阵，为n＋1行，m＋1列。将第0行和第0列都初始化为0。

2. 遍历matrix，根据公式 sum[i][j] = matrix[i - 1][j - 1] + sum[i][j - 1] + sum[i - 1][j] -sum[i - 1][j - 1] 计算所有sum。

3. 然后计算每个窗口的sum，根据公式 sum = sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k] 即整个大窗口剪去上面一部分和左边一部分再加回被重复减去的部分，即为当前窗口值

代码如下：

public class Solution {
    /**
     * @param matrix an integer array of n * m matrix
     * @param k an integer
     * @return the maximum number
     */
    public int maxSlidingWindow2(int[][] matrix, int k) {
        // Write your code here
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0 || k > matrix.length || k > matrix[0].length){
            return 0;
        }

        int n = matrix.length;
        int m = matrix[0].length;
        int[][] sum = new int[n + 1][m + 1];

        for(int i = 0; i <= n; i++){
            sum[i][0] = 0;
        }

        for(int j = 1; j <= m; j++){
            sum[0][j] = 0;
        }

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

        int max = Integer.MIN_VALUE;
        for(int i = k; i <= n; i++){
            for(int j = k; j <= m; j++){
                int temp = sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k];
                max = Math.max(max, temp);
            }
        }

        return max;
    }
}