题目--滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例:
输入: 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 |
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
思路
暴力解法
顺序求出每个窗口的最大值，复杂度O(nk)
自己的python
max_list = [max(nums[:k])]
for index,e in enumerate(nums):
if index<k: continue
max_list.append(max(nums[index-k+1:index+1]))
return max_list
官方python代码
n = len(nums)
//判断n,k是否有一个为0
if n * k == 0:
return []
return [max(nums[i:i + k]) for i in range(n - k + 1)]
双端队列
题目是要求出给定窗口大小内的最大值，可以考虑在一定的范围内，如果某个数小于它给定距离内的之后的数，那么这个数可以不用存储下来，比如队列[6 5 1 2 3 1 2]，窗口大小为3，那么在不管是[1 2 3]还是[2 3 1]，最大的值为3，在3进入到窗口时，2可以直接删除，我们不需要在储存这个值，只需要储存3即可。
这样的特性要求一个可以左端进行插入、删除，右端同样可以进行插入、删除操作的数据结构，因此选择使用双端队列来完成。
使用双端队列来完成有以下几个步骤：
- 初始化：我们首先初始化前k个值，将前k个值依照逻辑存储在双端队列中
- 窗口滑动：从第k个数开始，依次进行窗口滑动，同时记录当前窗口的最大值，即队列最左边的值。
- 窗口处理逻辑：每当滑动一次窗口，有新的值要入队时，我们首先对队列进行处理，判断当前队首是否处在窗口外，如果处在窗口外，将其出队。然后从队尾开始依次判断队尾的元素是否比当前要入队的值小，如果小则将其从队尾出队，否则不进行处理，直到队列中没有比要入队的值小的数或者队列中为空。然后将该值入队即可。
其中为了方便判断数字何时应该从窗口中出去，队列中存储的是数字的索引。这里的队列中是单调递减队列。
由于双向队列的特性，插入和删除的复杂度均为O(1)，每个元素均入队和出队一次，因此时间复杂度为O(n)，空间复杂度为O(n)
python代码
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
max_deque = deque()
# 入队逻辑，处理队列中的值
def clean_q(index):
if max_deque and max_deque[0] == index-k:
max_deque.popleft()
while max_deque and nums[max_deque[-1]] <= nums[index]:
max_deque.pop()
max_deque.append(index)
# init deque
for i in range(k):
clean_q(i)
max_inputs = [nums[max_deque[0]]]
for j in range(k, len(nums)):
clean_q(j)
max_inputs.append(nums[max_deque[0]])
return max_inputs
c++代码
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> max;
deque<int> window;
for(int i=0; i < nums.size(); i++){
if(!window.empty() && window.front() == i-k){
window.pop_front();
}
while(!window.empty() && nums[window.back()] < nums[i]){
window.pop_back();
}
window.push_back(i);
if(i >= k-1) max.push_back(nums[window.front()]);
}
return max;
}
};
贪心
使用两个数组，left和right遍历
class Solution:
def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':
n = len(nums)
if n * k == 0:
return []
if k == 1:
return nums
left = [0] * n
left[0] = nums[0]
right = [0] * n
right[n - 1] = nums[n - 1]
for i in range(1, n):
# from left to right
if i % k == 0:
# block start
left[i] = nums[i]
else:
left[i] = max(left[i - 1], nums[i])
# from right to left
j = n - i - 1
if (j + 1) % k == 0:
# block end
right[j] = nums[j]
else:
right[j] = max(right[j + 1], nums[j])
output = []
for i in range(n - k + 1):
output.append(max(left[i + k - 1], right[i]))
return output
