Leetcode 239. Sliding Window Maximum

Problem

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Algorithm

Monotonic Queue. A monotonic queue is used to store a decreasing sequence. If the current element is greater than the last element of the queue, we remove elements from the queue until the last element of the queue is smaller than the current element, or the queue becomes empty. Then, the current element is stored in the queue. The element at the front of the queue is also controlled by the length k.
Code

1. class Solution:
2.     def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
3.         if not nums or not k:
4.             return []
5.         
6.         nums_size = len(nums)
7.         Q, L, R = [0] * nums_size, 0, 0
8.         ans = [nums[0]] * nums_size
9.         for i in range(1, nums_size):
10.             while L <= R and nums[Q[R]] <= nums[i]:
11.                 R -= 1
12.             R += 1
13.             Q[R] = i
14.             if i - Q[L] + 1 > k:
15.                 L += 1
16.             ans[i] = nums[Q[L]]
17.         
18.         return ans[k-1:]

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告