給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。

返回滑動(dòng)窗口中的最大值。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sliding-window-maximum
解法一：暴力法：
解題思路：

移動(dòng)窗口計(jì)算每一個(gè)窗口的最大值

將步驟1得到的值加入要返回的列表中

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:# 暴力法時(shí)間復(fù)雜度O（Nk） 直接超出時(shí)間限制res = []if k<1 or k>len(nums):return res left = 0right = k - 1while right<len(nums):maxval = self.maxvalue(left,right,nums)res.append(maxval)left += 1right += 1return resdef maxvalue(self,left,right,nums):maxval = nums[left]while left<=right:if maxval<nums[left]:maxval = nums[left]return maxval

解法二：單調(diào)隊(duì)列法
解題思路：

如果隊(duì)列最左側(cè)索引已不在滑動(dòng)窗口范圍內(nèi)，彈出隊(duì)列最左側(cè)索引

通過(guò)循環(huán)確保隊(duì)列的最左側(cè)索引所對(duì)應(yīng)元素值最大

新元素入隊(duì)

從第一個(gè)滑動(dòng)窗口的末尾索引開(kāi)始將最大值存儲(chǔ)到結(jié)果res中

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:# 邊界條件if k * len(nums) == 0:return []# 優(yōu)化if k == 1:return numsfrom collections import dequeq = deque()# 單調(diào)隊(duì)列法：def clean_q()這個(gè)函數(shù)是精髓def clean_q(i):while q and q[0] <= i-k:q.popleft()while q and nums[q[-1]] < nums[i]:q.pop()q.append(i)res = []for i in range(k):clean_q(i)res.append(nums[q[0]])for i in range(k,len(nums)):clean_q(i)res.append(nums[q[0]])return res

總結(jié)

以上是生活随笔為你收集整理的滑动窗口最大值-leetcode 239题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。