LeetCode239. 滑动窗口最大值🌟🌟🌟🌟困难
课后作业
问题描述
原文链接：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] <= 1041 <= k <= nums.length
代码实现
Java
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
int index = 0;
for(int i = 0 ; i < nums.length; i++){
while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
deque.pollLast();
}
deque.add(i);
if(i - deque.peek() >= k){
deque.poll();
}
if(i + 1 >= k){
res[index++] = nums[deque.peek()];
}
}
return res;
}
}
Python
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
deque = collections.deque()
res = []
for i in range(len(nums)):
while deque and nums[deque[-1]] <= nums[i]:
deque.pop()
deque.append(i)
if deque[0] == i-k:
deque.popleft()
if i >= k-1:
res.append(nums[deque[0]])
return res
C++
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q;
vector<int> res;
for(int i = 0; i < nums.size(); i++){
while(!q.empty() && nums[q.back()] <= nums[i]){
q.pop_back();
}
q.push_back(i);
if(q.front() == i-k){
q.pop_front();
}
if(i >= k-1){
res.push_back(nums[q.front()]);
}
}
return res;
}
};
Go
func maxSlidingWindow(nums []int, k int) []int {
var q []int
res := []int{}
for i := 0; i < len(nums); i++ {
for len(q) > 0 && nums[q[len(q)-1]] <= nums[i] {
q = q[:len(q)-1]
}
q = append(q, i)
if q[0] == i-k {
q = q[1:]
}
if i >= k-1 {
res = append(res, nums[q[0]])
}
}
return res
}