本问题对应的 leetcode 原文链接：剑指 Offer 59 – I. 滑动窗口的最大值
问题描述
给定一个数组 nums 和滑动窗口的大小 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 ≤ nums.length。
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length <= 1){
return nums;
}
LinkedList<Integer> queue = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
int index = 0;
//K
for(int i = 0; i < nums.length; i++){
while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
queue.pollLast();
}
queue.add(i);
if(queue.peekLast() - k == queue.peek()){
queue.poll();
}
if(i + 1 >= k){
res[index++] = nums[queue.peek()];
}
}
return res;
}
}
时间复杂度：O(n)
额外空间复杂的：O(k)
Python
from collections import deque
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or len(nums) < k:
return []
queue = deque()
res = []
for i in range(len(nums)):
while queue and nums[queue[-1]] <= nums[i]:
queue.pop()
queue.append(i)
if queue[0] == i - k:
queue.popleft()
if i >= k - 1:
res.append(nums[queue[0]])
return res
C++
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (nums.empty() || nums.size() < k) {
return vector<int>();
}
deque<int> queue;
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
while (!queue.empty() && nums[queue.back()] <= nums[i]) {
queue.pop_back();
}
queue.push_back(i);
if (queue.front() == i - k) {
queue.pop_front();
}
if (i >= k - 1) {
res.push_back(nums[queue.front()]);
}
}
return res;
}
};
Go
func maxSlidingWindow(nums []int, k int) []int {
if len(nums) < k || nums == nil {
return []int{}
}
queue := make([]int, 0)
res := make([]int, 0)
for i := 0; i < len(nums); i++ {
for len(queue) > 0 && nums[queue[len(queue)-1]] <= nums[i] {
queue = queue[:len(queue)-1]
}
queue = append(queue, i)
if queue[0] == i-k {
queue = queue[1:]
}
if i >= k-1 {
res = append(res, nums[queue[0]])
}
}
return res
}
JS
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
if (!nums || nums.length < k) {
return [];
}
const queue = [];
const res = [];
for (let i = 0; i < nums.length; i++) {
while (queue.length && nums[queue[queue.length - 1]] <= nums[i]) {
queue.pop();
}
queue.push(i);
if (queue[0] === i - k) {
queue.shift();
}
if (i >= k - 1) {
res.push(nums[queue[0]]);
}
}
return res;
};
shuaidi