LeetCode-239 滑动窗口最大值

Table of Contents

LeetCode-239 滑动窗口最大值 #

Solution 1 #

遇到一个数, 那么它之前的比它小的数都不可能成为当前窗口的最大数. 我们维护一个单调增的队列.

代码如下:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        for i, x in enumerate(nums):
            while q and nums[q[-1]] <= x:
                q.pop()
            q.append(i)
            if q and i - q[0] >= k:
                q.popleft()
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans