LeetCode 239 Sliding Window Maximum

LeetCode 239 Sliding Window Maximum

<div>

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.

Example 1:

<pre>Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max

---

[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 ** 5** 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 </pre>

Example 2:

<pre>Input: nums = [1], k = 1 Output: [1] </pre>

Constraints:

• 1 <= nums.length <= 10<sup>5</sup>
• -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
• 1 <= k <= nums.length

</div>

算法思路：

LL(queue) + 递减栈
难点是什么时候输出结果，并不是出栈时候，而是每轮遍历时，就可以计算当轮的最大值，也就是当前的队首。此题也可以用heap，实现几乎一样，但时间复杂度是nlogn

注意事项：

1. 每轮遍历时，计算当轮的最大值就是当前的队首，用queue[0]而不是queue[-1]
2. 注意程序顺序，先递减栈模板，在计算结果，最后移出越界元素。如例子[876], i = 2, 窗口大小满足了，计算结果为8,8在下一轮会越界，所以移除。
3. 结果数小于数组大小，注意line 7的条件

Python代码：

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	queue, res = deque(), []
	for i in range(len(nums)):
		while queue and nums[i] > nums[queue[-1]]:
			queue.pop()
		queue.append(i)
		if i >= k - 1:
			res.append(nums[queue[0]])#attn queue[0] not -1
		if i - queue[0] + 1 >= k: #attn queue[0] not -1
			queue.popleft()
return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)