题目
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
————— —–
[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
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
- 1 <= k <= nums.length
我的代码（Python）
version 1
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
result = []
print(f'k: {k}')
if k == 1:
result = nums
elif k % 2 == 0:
semi_result = self.maxSlidingWindow(nums, k // 2)
for i in range(len(nums) - k + 1):
result.append(max(semi_result[i], semi_result[i + k // 2]))
else:
semi_result1 = self.maxSlidingWindow(nums, k // 2)
semi_result2 = self.maxSlidingWindow(nums, k - k // 2)
for i in range(len(nums) - k + 1):
result.append(max(semi_result1[i], semi_result2[i + k // 2]))
return result暴力解法肯定是不行的，O(n)O(k)。这样大概可以化简到O(n)O(lgk)，不过重复计算过多，实现前就推测应该不行。
结果不出所料，超时了。
version 2
class Solution:
def calculateResult(self, nums: List[int], k: int, inter_results: List[List[int]]) -> None:
if len(inter_results[k - 1]) > 0:
return inter_results[k - 1]
if k % 2 == 0:
m = k // 2
self.calculateResult(nums, m, inter_results)
for i in range(len(nums) - k + 1):
inter_results[k - 1].append(max(inter_results[m - 1][i], inter_results[m - 1][i + m]))
else:
m = k // 2
n = k - m
self.calculateResult(nums, m, inter_results)
self.calculateResult(nums, n, inter_results)
for i in range(len(nums) - k + 1):
inter_results[k - 1].append(max(inter_results[m - 1][i], inter_results[n - 1][i + m]))
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
inter_results = [nums] + [[] for _ in range(k - 1)]
print(f'inter_results: {inter_results}')
self.calculateResult(nums, k, inter_results)
return inter_results[k - 1]虽然通过了，但是时间和空间都在末5%左右。
迭代虽然比较容易理解和实现，但是在效率上并不好。
只是结果这么差，感觉上不是这个问题，还是方向本身有误。
for i in range(len(nums) - k + 1):
inter_results[k - 1].append(max(inter_results[m - 1][i], inter_results[m - 1][i + m], nums[i + k - 1]))把计算处奇数的计算方式优化如上，时间上没有多少提升，内存上略有优化，可见还是方向不对。
点评
参考了官方的答案。官方给出了三种方式，我的方案实际上算是第三种方案，预处理。
官方的第一种答案又是惯例的标准库中的数据结构和函数的使用，排序、插入和删除（此处是使用最大堆）都达到最优化方案。对python来说是heapq。
不过第二种答案单调双端队列确实非常巧妙，不是很容易想得到的。简单来说就是保证队列里的每一个值，在往前最大k – 1，往后最大k的范围内是最大的。