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

更新於 發佈於 閱讀時間約 3 分鐘

題目敘述

給定一個方陣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)


關鍵知識點

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

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


Reference

[1] Largest Local Values in a Matrix - LeetCode

avatar-img
90會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
題目敘述 輸入給定一個整數陣列,分別代表每小朋友的快樂值。 要求我們選擇其中最快樂的k位小朋友,累加這群小朋友的快樂值。 有一個特殊的規則,第一位選中的小朋友快樂值不變。 接著,第二位選中的小朋友快樂值-1 再接著,第三位選中的小朋友快樂值-2 快樂值扣到只剩下0就不再往下扣 .
題目敘述 輸入給定一個整數陣列,分別代表每位運動員在比賽中的成績。 分數最高的給予金牌"Gold Medal" 分數次高的給予金牌"Silver Medal" 分數第三高的給予金牌"Bronze Medal" 剩餘的名次依照順序給予"4", "5", ..., "n" 的編號。 輸出時以字串
題目敘述 輸入給定一個鏈結串列,整體看代表一個十進位的數字,各別看每個節點代表每個digit,分別從最高位~最低位個位數。 要求我們把原本的數字乘以二,並且以鏈結串列的形式返回答案。 原本的英文題目敘述
題目敘述 題目給定一個鏈結串列中的節點Node,要求我們從鏈結串列中刪除該節點。 題目保證該節點不是tail node。 題目要求我們in-place原位操作。 原本的英文題目敘述 測試範例 Example 1: Input: head = [4,5,1,9], node = 5
題目敘述 輸入給定一個鏈結串列的head node。 要求我們進行化簡,只要某個節點的右手邊存在比較大的節點,就刪除掉。 例如 5->2->13->3 5的右手邊有13,所以5刪除掉。 2的右手邊有13,所以2刪除掉。 13的右手邊沒有更大的節點,所以13留著。 3的右手邊沒有更大
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
題目敘述 輸入給定一個整數陣列,分別代表每小朋友的快樂值。 要求我們選擇其中最快樂的k位小朋友,累加這群小朋友的快樂值。 有一個特殊的規則,第一位選中的小朋友快樂值不變。 接著,第二位選中的小朋友快樂值-1 再接著,第三位選中的小朋友快樂值-2 快樂值扣到只剩下0就不再往下扣 .
題目敘述 輸入給定一個整數陣列,分別代表每位運動員在比賽中的成績。 分數最高的給予金牌"Gold Medal" 分數次高的給予金牌"Silver Medal" 分數第三高的給予金牌"Bronze Medal" 剩餘的名次依照順序給予"4", "5", ..., "n" 的編號。 輸出時以字串
題目敘述 輸入給定一個鏈結串列,整體看代表一個十進位的數字,各別看每個節點代表每個digit,分別從最高位~最低位個位數。 要求我們把原本的數字乘以二,並且以鏈結串列的形式返回答案。 原本的英文題目敘述
題目敘述 題目給定一個鏈結串列中的節點Node,要求我們從鏈結串列中刪除該節點。 題目保證該節點不是tail node。 題目要求我們in-place原位操作。 原本的英文題目敘述 測試範例 Example 1: Input: head = [4,5,1,9], node = 5
題目敘述 輸入給定一個鏈結串列的head node。 要求我們進行化簡,只要某個節點的右手邊存在比較大的節點,就刪除掉。 例如 5->2->13->3 5的右手邊有13,所以5刪除掉。 2的右手邊有13,所以2刪除掉。 13的右手邊沒有更大的節點,所以13留著。 3的右手邊沒有更大
你可能也想看
Google News 追蹤
Thumbnail
隨著理財資訊的普及,越來越多台灣人不再將資產侷限於台股,而是將視野拓展到國際市場。特別是美國市場,其豐富的理財選擇,讓不少人開始思考將資金配置於海外市場的可能性。 然而,要參與美國市場並不只是盲目跟隨標的這麼簡單,而是需要策略和方式,尤其對新手而言,除了選股以外還會遇到語言、開戶流程、Ap
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
高中數學主題練習—平面向量內積計算 解答:
Thumbnail
高中數學主題練習—求空間中平面
Thumbnail
隨著理財資訊的普及,越來越多台灣人不再將資產侷限於台股,而是將視野拓展到國際市場。特別是美國市場,其豐富的理財選擇,讓不少人開始思考將資金配置於海外市場的可能性。 然而,要參與美國市場並不只是盲目跟隨標的這麼簡單,而是需要策略和方式,尤其對新手而言,除了選股以外還會遇到語言、開戶流程、Ap
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
高中數學主題練習—平面向量內積計算 解答:
Thumbnail
高中數學主題練習—求空間中平面