LeetCode 239 Sliding Window Maximum

LeetCode 239 Sliding Window Maximum

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:

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

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

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

算法思路：

LL + 递减栈
难点是什么时候输出结果，并不是出栈时候，而是每轮遍历时，就可以计算当轮的最大值，也就是当前的队首

注意事项：

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

Python代码：

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	queue, res = collections.deque(), []
	for i in range(len(nums)):
		while queue and nums[i] > nums[queue[-1]]:
			queue.pop()
		queue.append(i)

		if i + 1 >= k:
			res.append(nums[queue[0]])
		if i - queue[0] + 1 >= k:
			queue.popleft()
	return res

算法分析：

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