Description
Given an array of
n * m matrix, and a moving matrix window (size k * k), move the window from top left to bottom right at each iteration, find the maximum sum inside the window at each moving.Return 0 if the answer does not exist.
Example
Example 1:
Input：[[1,5,3],[3,2,1],[4,1,9]]，k=2
Output：13
Explanation：
At first the window is at the start of the matrix 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.
Example 2:
Input：[[10]，k=1
Output：10
Explanation：
sliding window size is 1*1，and return 10.
Challenge
O(n^2) time.
思路：
考点：
- 二维前缀和
题解：
- sum[i][j]存储左上角坐标为(0,0),右下角坐标为(i,j)的子矩阵的和。
- sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];递推求值即可，两部分相加，减去重复计算部分。
- int value = sum[i][j] - sum[i - k][j] -sum[i][j - k] + sum[i - k][j - k];可求得一个k * k大小子矩阵的和。
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) { // Write your code here int n = matrix.length; if (n == 0 || n < k) return 0; int m = matrix[0].length; if (m == 0 || m < k) return 0; int[][] sum = new int[n + 1][m + 1]; for (int i = 0; i <= n; ++i) sum[i][0] = 0; for (int i = 0; i <= m; ++i) sum[0][i] = 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 - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; int max_value = Integer.MIN_VALUE; for (int i = k; i <= n; ++i) for (int j = k; j <= m; ++j) { int value = sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k]; if (value > max_value) max_value = value; } return max_value; } }