題目敘述
給定一個方陣grid，請計算每個3x3窗口內的最大值，並且也以方陣的形式輸出答案。
測試範例
Example 1:Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
Output: [[9,9],[8,6]]
Explanation: The diagram above shows the original matrix and the generated matrix.
Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.
Example 2:
Input: grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
Output: [[2,2,2],[2,2,2],[2,2,2]]
Explanation: Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.
約束條件
Constraints:
n == grid.length == grid[i].length
輸入矩陣grid一定是方陣。
3 <= n <= 100
輸入矩陣的邊常介於 3 ~ 100之間。
1 <= grid[i][j] <= 100
陣列元素介於1~100之間。
演算法 模擬法
依題意進行模擬，從左到右，由上到下，掃描過每個3x3窗口，將每個窗口的最大值儲存起來。
程式碼 模擬法
class Solution:
def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
n = len(grid)
res = []
# on each grid cell
for i in range(n - 2):
ans = []
for j in range(n - 2):
max_value = 0
# scan each 3x3 sliding window
for a in range(i, i + 3):
for b in range(j, j + 3):
max_value = max(max_value, grid[a][b])
# save maximal value
ans.append(max_value)
res.append(ans)
return res
複雜度分析
時間複雜度: O(n^2)
n^2個格子點，每個格子點要掃描3x3固定尺寸大小的滑動窗口。
空間複雜度: O(n^2)
輸出空間O( (n-2)^2)和輸入order相同，皆為O(n^2)
關鍵知識點
滑動窗口大小固定，依照題意進行模擬即可。
如果滑動窗口比較大，可以使用單調隊列加速。
