鶴立雞群 滑動窗口的最大值 Leetcode #2373

Anthony DELANOIX on Unsplash

題目敘述

給定一個方陣grid，請計算每個3x3窗口內的最大值，並且也以方陣的形式輸出答案。

測試範例

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)

關鍵知識點

滑動窗口大小固定，依照題意進行模擬即可。

如果滑動窗口比較大，可以使用單調隊列加速。

Reference

[1] Largest Local Values in a Matrix - LeetCode