239. 滑动窗口最大值
给定一个数组 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提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
进阶：
你能在线性时间复杂度内解决此题吗？
解法一
暴力 O(n*k)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
if not n*k: return []
return [max(nums[i:i+k]) for i in range(n-k+1)]
超出时间限制
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
if nums != []:
tmp_max = max(nums[0:k])
for i in range(len(nums) - (k - 1)):
tmp_max = max(nums[i:i+k])
res.append(tmp_max)
return res
解法二
MaxHeap a. 维护 堆顶元素，时间复杂度为 O(logk) b. 结果 Max 为 堆顶元素，查询复杂度为 O(1)
解法三
deque(sliding window) O(n+k)----(k与n为一个数量级)----> O(n)
https://leetcode.com/problems/sliding-window-maximum/discuss/65901/9-lines-Ruby-11-lines-Python-O(n)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
d = collections.deque()
result = []
for i,n in enumerate(nums):
while d and nums[d[-1]] < n:
d.pop()
d += i,
if d[0] == i-k:
d.popleft()
if i >= k-1:
result += nums[d[0]],
return result
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums: return []
window, res = [], []
for i, x in enumerate(nums):
if i >= k and window[0] <= i - k:
window.pop(0)
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
if i >= k -1:
res.append(nums[window[0]])
return res
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int [] result = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
if(!deque.isEmpty() && deque.getFirst() == i - k) deque.removeFirst(); // 移除不在窗口中的元素
while(!deque.isEmpty() && nums[i] > nums[deque.getLast()]) deque.removeLast(); // 移除比当前元素小的元素
deque.addLast(i);
if (i < k-1) continue; // 等待 i 滑过 k-1 个后，再往结果集中添加元素
result[i-k+1] = nums[deque.getFirst()];
}
return result;
}
}