【Day 28 】2022-11-28 - 239. 滑动窗口最大值

[azl397985856]

239. 滑动窗口最大值

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/sliding-window-maximum/

前置知识

• 队列
• 滑动窗口

  题目描述

  
  给定一个数组 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

[whoam-challenge]

思路

优先队列

代码

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) q = [(-nums[i], i) for i in range(k)] heapq.heapify(q)

    ans = [-q[0][0]]
    for i in range(k, n):
        heapq.heappush(q, (-nums[i], i))
        while q[0][1] <= i - k:
            heapq.heappop(q)
        ans.append(-q[0][0])

    return ans

复杂度分析

-时间复杂度O(nlogn) -空间复杂度 O(n)

[FlipN9]

/**
    将链表 切分成大小为 k 的 chunk
    然后 left 记录在 chunk 内从左往右的最大值, 
         right 记录 chunk 内从右往左的最大值
    滑动窗口只需要找 right[i] 和 left[i + k - 1]的最大值

            1  3  -1  * -3  5  3  *  6  7
    left    1  3  3     -3  5  5     6  7
    right   3  3  -1     5  5  3     7  7

    TC: O(N)    SC: O(N) 4ms

*/
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int N = nums.length;
        int[] res = new int[N - k + 1];
        int[] left = new int[N];
        int[] right = new int[N];
        for (int i = 0; i < N; i += k) {
            int max = Integer.MIN_VALUE;
            int rightBound = Math.min(i + k - 1, N - 1);
            // from left to right --> 
            for (int j = i; j <= rightBound; j++) {
                if (nums[j] > max) 
                    max = nums[j];
                left[j] = max;
            }
            // from right to left <--
            max = Integer.MIN_VALUE;
            for (int j = rightBound; j >= i; j--) {
                if (nums[j] > max)
                    max = nums[j];
                right[j] = max;
            }
        }
        for (int i = 0; i < N - k + 1; i++) {
            int j = i + k - 1;
            res[i] = Math.max(right[i], left[j]);
        }
        return res;
    }
}

/**
    维护一个 单调递减 的 Monotonic Queue, 尾进头出
    TC: O(n)    SC: O(k)
    36ms
*/
class Solution1 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int N  = nums.length;
        int[] res = new int[N - k + 1];
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            // 保证窗口内 从大到小, 如果前面的数小则需要一次弹出, 直到满足要求
            while (!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.addLast(i);
            // 判断队首的值是否在 k 的滑动窗口内
            if (queue.peekFirst() <= i - k) {
                queue.poll();
            }
            // 当增长到窗口长度为k时 保存当前窗口中最大值
            if (i + 1 - k >= 0) {
                res[i + 1 - k] = nums[queue.peekFirst()];
            }
        }
        return res;
    }
}

[wurongronga]

思路 单调队列

class Solution:
    '''
    1. create a deque for indexes, and res list
    2. loop through the nums
        1. if cur number is greater than the deque left number
            pop out all elements in deque
            append index of the cur number into deque
        2. if cur is smaller than the deque left number 
            append index of the cur number into deque
        3. if the deque left number is out of the window 
            remove it from deque

    '''

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        res = []

        for i, cur in enumerate(nums):
            # when the cur number is larger than the prev max, clear the deque
            while q and cur > nums[q[0]]:
                q.popleft()
            # add cur index into deque
            q.append(i)

            # if out of window, remove the deque left
            if q[0] == i - k:
                q.popleft()

            # start append result as long as we have a complete window 
            if i >= k - 1:   
                res.append(nums[q[0]])

        return res

[heng518]

class Solution { public: vector maxSlidingWindow(vector& nums, int k) { vector res; int left = (int)malloc(sizeof(int) nums.size()); int right = (int)malloc(sizeof(int) nums.size());

    *left = nums[0];
    *(right + nums.size() - 1) = nums[nums.size() - 1];

    for(int i = 1; i < nums.size(); i++)
    {
        left[i] = (i % k == 0) ? nums[i] : max(left[i-1], nums[i]);

        int j = nums.size() - i - 1;

        right[j] = (j % k == 0) ? nums[j] : max(right[j+1], nums[j]);
    }

    for(int i = 0; i + k <= nums.size(); i++)
    {
        res.push_back(max(right[i], left[i+k-1]));     
    }

    return res;
}

};

[yin02]

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) q = [(-nums[i], i) for i in range(k)] heapq.heapify(q)

ans = [-q[0][0]]
for i in range(k, n):
    heapq.heappush(q, (-nums[i], i))
    while q[0][1] <= i - k:
        heapq.heappop(q)
    ans.append(-q[0][0])

return ans

[chenming-cao]

解题思路

单调队列。不需要储存窗口内所有的元素。如果新进入的元素比前面的大，可以直接将前面的元素移除。这样每一时刻我们都会得到一个单调递减队列，队首元素为最大值。 具体做法：入队列。然后移除失效元素，包括(1) 超出窗口范围的元素，(2) 队列尾部小于当前值的元素。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        int n = nums.length;
        int[] res = new int[n - k + 1];
        res[0] = nums[queue.peekFirst()];
        for (int i = k; i < n; i++) {
            while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
            if (queue.peekFirst() < i - k + 1) {
                queue.pollFirst();
            }
            res[i - k + 1] = nums[queue.peekFirst()];
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为数组长度
• 空间复杂度：O(k)，需要队列，队列中不超过k元素

[zrtch]

var maxSlidingWindow = function(nums, k) {
 const n = nums.length;
    const q = [];
    for (let i = 0; i < k; i++) {
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        q.push(i);
    }

    const ans = [nums[q[0]]];
    for (let i = k; i < n; i++) {
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        q.push(i);
        while (q[0] <= i - k) {
            q.shift();
        }
        ans.push(nums[q[0]]);
    }
    return ans;

};

[bookyue]

code

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> queue = new ArrayDeque<>(k);

        for (int i = 0; i < n; i++) {
            if (!queue.isEmpty() && queue.getFirst() <= i - k)
                queue.removeFirst();

            while (!queue.isEmpty() && nums[queue.getLast()] < nums[i])
                queue.removeLast();

            queue.addLast(i);

            if (i >= k - 1) res[i - k + 1] = nums[queue.getFirst()];
        }

        return res;
    }

[ringo1597]

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

[buer1121]

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

暴力法

    if k==0: return []
    res=[]
    for r in range(k-1,len(nums)):
        res.append(max(nums[r-k+1:r+1]))
    return  res

    ###双向队列解法，由于暴力法超时
    if k==0: return nums
    res=[]
    from collections import deque
    queue=deque()
    #第一个窗口
    for i in range(k):
        while len(queue)!=0 and nums[i]>nums[queue[-1]]:
            queue.pop()
        queue.append(i)

    for i in range(k,len(nums)):
        res.append(nums[queue[0]])
        #已经不是当前窗口了
        while len(queue)!=0 and queue[0]<i-k+1:
            queue.popleft()
        #对于当前窗口保存最大值
        while len(queue)!=0 and nums[queue[-1]]<nums[i]:
            queue.pop()
        queue.append(i)

    res.append(nums[queue[0]])
    return res

[954545647]

思路

暴力法 & 双向队列

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
 var maxSlidingWindow = function(nums, k) {
  let res = [];
  for(let i = 0; i < nums.length - k+1; i++){
    const curMax = cal(nums,i,i+k);
    res.push(curMax)
  }
  return res
};

function cal(nums,start,end){
  console.log('start,end ==>',start,end)
  let max = nums[start];
  for(let i= start; i < end; i++){
    max = Math.max(nums[i],max)
  }
  return max;
}

var maxSlidingWindow = function (nums, k) {
  const res = [];
  const dequeue = new Dequeue([]);
  // 前 k - 1 个数入队
  for (let i = 0; i < k - 1; i++) {
    dequeue.push(nums[i]);
  }

  // 滑动窗口
  for (let i = k - 1; i < nums.length; i++) {
    dequeue.push(nums[i]);
    res.push(dequeue.max());
    dequeue.shift(nums[i - k + 1]);
  }
  return res;
};

class Dequeue {
  constructor(nums) {
    this.list = nums;
  }

  push(val) {
    const nums = this.list;
    // 保证数据从队头到队尾递减
    while (nums[nums.length - 1] < val) {
      nums.pop();
    }
    nums.push(val);
  }

  // 队头出队
  shift(val) {
    let nums = this.list;
    if (nums[0] === val) {
      nums.shift();
    }
  }

  max() {
    return this.list[0];
  }
}
console.log(' ==>',maxSlidingWindow([1,3,-1,-3,5,3,6,7],3))

复杂度分析

[Ryanbaiyansong]

··· class MQ: def init(self): self.q = deque() self.maxq = deque()

def add(self, val):
    self.q.append(val)

    while self.maxq and self.maxq[-1] < val:
        self.maxq.pop()
    self.maxq.append(val)

def pop(self):
    val = self.q.popleft()
    if val == self.maxq[0]:
        self.maxq.popleft()

def max(self):
    return self.maxq[0]

def size(self):
    return len(self.q)

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) window = MQ() res = [] for i, v in enumerate(nums): window.add(v) if window.size() == k: res.append(window.max()) window.pop()

    # print(res)
    return res

···

[Alyenor]

function maxSlidingWindow(nums: number[], k: number): number[] {
    let res=[],q=[]
    for(let i=0;i<nums.length;i++){
        if(q.length&&i-k+1>q[0]) q.shift()
        while(q.length && nums[i] > nums[q[q.length - 1]]) q.pop()
        q.push(i)
        if(i>=k-1) res.push(nums[q[0]])
    }
    return res
};

[Elsa-zhang]

'''239. 滑动窗口最大值
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
'''

import heapq

class Solution:
    def shiftwindow(self, nums:list, k:int):
        # # 超时了 O(nk)
        # if not nums or not k:
        #     return None

        # ans = []
        # for i in range(len(nums)-k+1):
        #     window = nums[i:i+k]
        #     ans.append(max(window))

        # return ans

        # 堆
        n = len(nums)
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)

        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i-k:
                heapq.heappop(q)
            ans.append(-q[0][0])    

        return ans

[mayloveless]

思路

单调队列

代码

var maxSlidingWindow = function(nums, k) {
    const n = nums.length;
    // 当前窗口最大值的index
    const q = [];
    // 先进入k个数字
    for (let i = 0; i < k; i++) {
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        q.push(i);
    }

    const ans = [nums[q[0]]];
    for (let i = k; i < n; i++) {
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        q.push(i);
        while (q[0] <= i - k) {
            // 过了窗口界限
            q.shift();
        }
        ans.push(nums[q[0]]);
    }
    return ans;
};

复杂度

时间O(n) 空间O(n)

[Abby-xu]

思路

抄作业：2 max stacks

代码

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        class MaxStack:
            def __init__(self):
                self._stack = []
                self._max_stack = []

            def push(self, item):
                self._stack.append(item)
                self._max_stack.append(
                    max(item, self._max_stack[-1]) if self._max_stack else item
                )

            def pop(self):
                self._max_stack.pop()
                return self._stack.pop()

            def get_max(self):
                return self._max_stack[-1] if self._max_stack else int(-1e6)

            def empty(self):
                return not self._stack

        left = MaxStack()
        right = MaxStack()
        answer = []

        for ind in range(k):
            left.push(nums[ind])

        for ind in range(k, len(nums)):
            if right.empty():
                while not left.empty():
                    right.push(left.pop())

            answer.append(max(left.get_max(), right.get_max()))
            left.push(nums[ind])
            right.pop()
        answer.append(max(left.get_max(), right.get_max()))
        return answer

复杂度

。。。

[klspta]

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || k < 1 || nums.length < k){
            return null;
        }

        LinkedList<Integer> qmax = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];

        int index = 0;

        for(int R = 0; R < nums.length; R++){
            while (!qmax.isEmpty() && nums[qmax.peekLast()] <= nums[R]){
                qmax.pollLast();
            }
            qmax.addLast(R);
            if(qmax.peekFirst() == R - k){
                qmax.pollFirst();
            }
            if(R >= k - 1){
                result[index++] = nums[qmax.peekFirst()];
            }
        }
        return result;
    }

[jackgaoyuan]

func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) < k {
        return []int{}
    }
    var descDeque []Item
    res := make([]int, len(nums))
    for i := 0; i < len(nums); i++ {
        left := i - k + 1
        // remove item out of window
        for len(descDeque) > 0 {
            if descDeque[0].Idx < left {
                descDeque = descDeque[1:]
            } else {
                break
            }
        }
        // remove item in descDeque which smaller than inserted item
        for len(descDeque) > 0 && descDeque[len(descDeque) - 1].Value < nums[i] {
            descDeque = descDeque[:len(descDeque) - 1]
        }
        // insert item
        descDeque = append(descDeque, Item{ Value: nums[i], Idx: i })
        res[i] = descDeque[0].Value
    }
    return res[k-1:]
}

type Item struct {
    Value int
    Idx int
}

Time: O(n) Space: O(n)

[yuexi001]

思路

• 单调递减队列q.front()为当前窗口最大值

代码

C++ Code:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>res;
        deque<int>q; //存储nums索引,单调递减队列
        for(int i = 0; i < nums.size(); i++){
            //队列非空，且q.front()不在滑动窗口内
            if(!q.empty() && (i - k + 1) > q.front()){
                q.pop_front();
            }
            //队列非空，且nums[i] > nums[q.back()]，删除队列中小于当前元素的值，保证队列递减
            while(!q.empty() && nums[i] > nums[q.back()]){
                q.pop_back();
            }
            //索引入队
            q.push_back(i);
            //保存每个窗口最大值
            if((i - k + 1) >= 0){
                res.push_back(nums[q.front()]);
            }

        }
        return res;
    }
};

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(k)$

[StaringWhere]

思路

滑动窗口+最大最小 = 单调队列

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> mono;
        vector<int> res;
        for (int i = 0; i < k; i++) {
            while (!mono.empty() && nums[mono.back()] < nums[i]) {
                mono.pop_back();
            }
            mono.push_back(i);
        }
        res.push_back(nums[mono.front()]);
        for (int i = k; i < nums.size(); i++) {
            if (mono.front() < i - k + 1) {
                mono.pop_front();
            }
            while (!mono.empty() && nums[mono.back()] < nums[i]) {
                mono.pop_back();
            }
            mono.push_back(i);
            res.push_back(nums[mono.front()]);
        }
        return res;
    }
};

复杂度分析

O(N) / O(K)

[zywang0]

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || k < 1 || nums.length < k){
            return null;
        }

        LinkedList<Integer> qmax = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];

        int index = 0;

        for(int R = 0; R < nums.length; R++){
            while (!qmax.isEmpty() && nums[qmax.peekLast()] <= nums[R]){
                qmax.pollLast();
            }
            qmax.addLast(R);
            if(qmax.peekFirst() == R - k){
                qmax.pollFirst();
            }
            if(R >= k - 1){
                result[index++] = nums[qmax.peekFirst()];
            }
        }
        return result;
    }

[snmyj]

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n=nums.size();
        int max=nums[0];
        vector<int> ans;
        if(n==1) {
             ans.push_back(nums[0]);
             return ans;
        }
        if(k==1){
            for(int i=0;i<n;i++){
                ans.push_back(nums[i]);
            }
            return ans;
        }

        for(int i=0;i<k-1;i++){
           if(nums[i]<nums[i+1]) max=nums[i+1];
           else max=nums[i];

        }
         ans.push_back(max);
        for(int i=1,j=k;j<n;i++,j++){
            if(nums[i]>max) max=nums[i];
            if(nums[j]>max) max=nums[j];
            ans.push_back(max);

        }
        return ans;

    }
};

[want2333]

【Day 28】239. 滑动窗口最大值

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

[xqmmy]

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque()
        res = []
        if k < 1:
            return res
        for i in range (k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
        res.append(nums[q[0]])
        for i in range (k, n):
            while q and q[0] <= i-k: 
                q.popleft()
            while q and nums[q[-1]] <= nums[i]:
                q.pop()
            q.append(i)
            res.append(nums[q[0]])
        return res ```

[tiandao043]

思路

一开始觉得是优先队列，看了题解发现单调队列更快，将索引存队列，注意出的时候，由于后续有更大的需要把前面比他小的清除，应该popback的，第一次写成了popfront，导致中间小数没被删掉，有些不专心。

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int mx=-1;
        vector<int> ans;
        list<int> l;
        l.push_back(0);
        for(int i=1;i<k;i++){        
            while(!l.empty()&&nums[l.back()]<nums[i]){
                l.pop_back();
            }
            l.push_back(i);
            // mx=max(mx,nums[i]);
        }
        ans.push_back(nums[l.front()]);
        for(int i=k;i<nums.size();i++){
            // cout<<nums[i]<<" "<<nums[l.front()]<<endl; 
            while(!l.empty()&&nums[l.back()]<nums[i]){
                l.pop_back();
            }
            // cout<<nums[i]<<" "<<nums[l.front()]<<endl; 
            l.push_back(i);            
            // cout<<nums[i]<<" "<<nums[l.front()]<<endl; 
            while(l.front()<=i-k){
                l.pop_front();
            }
            ans.push_back(nums[l.front()]);

        }        
        // for(auto a:l){
        //     cout<<a<<endl;
        // }
        return ans;

    }
};

合并

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int mx=-1;
        vector<int> ans;
        list<int> l;
        for(int i=0;i<nums.size();i++){
            while(!l.empty()&&nums[l.back()]<nums[i]){
                l.pop_back();
            }
            l.push_back(i);      
            while(l.front()<=i-k){
                l.pop_front();
            }
            if(i>=k-1)ans.push_back(nums[l.front()]);
        }      
        return ans;
    }
};

O(n) O(k)

[AstrKing]

思路

遍历数组，将 数 存放在双向队列中，并用 L,R 来标记窗口的左边界和右边界。队列中保存的并不是真的 数，而是该数值对应的数组下标位置，并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大，则需要弹出队尾值，直到队列重新满足从大到小的要求。刚开始遍历时，L 和 R 都为 0，有一个形成窗口的过程，此过程没有最大值，L 不动，R 向右移。当窗口大小形成时，L 和 R 一起向右移，每次移动时，判断队首的值的数组下标是否在 [L,R] 中，如果不在则需要弹出队首的值，当前窗口的最大值即为队首的数。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length < 2) return nums;
        // 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
        LinkedList<Integer> queue = new LinkedList();
        // 结果数组
        int[] result = new int[nums.length-k+1];
        // 遍历nums数组
        for(int i = 0;i < nums.length;i++){
            // 保证从大到小 如果前面数小则需要依次弹出，直至满足要求
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
                queue.pollLast();
            }
            // 添加当前值对应的数组下标
            queue.addLast(i);
            // 判断当前队列中队首的值是否有效
            if(queue.peek() <= i-k){
                queue.poll();   
            } 
            // 当窗口长度为k时 保存当前窗口中最大值
            if(i+1 >= k){
                result[i+1-k] = nums[queue.peek()];
            }
        }
        return result;
    }
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[testplm]

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        from collections import deque
        q = deque()
        res = []
        for i,cur in enumerate(nums):
            while q and nums[q[-1]]<cur:
                q.pop()
            q.append(i)
            if q[0] == i-k:
                q.popleft()
            if i>=k-1:
                res.append(nums[q[0]])
        return res

[Serena9]

代码

class MyQueue(object):
    def __init__(self):
        self.queue = []

    def pop(self, value):
        if self.queue and value == self.queue[0]:
            self.queue.pop(0)

    def push(self, value):
        while self.queue and value>self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)

    def front(self):
        return self.queue[0]

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        que = MyQueue()
        res = []
        for i in range(k):
            que.push(nums[i])
        res.append(que.front())
        for i in range(k, len(nums)):
            que.pop(nums[i-k])
            que.push(nums[i])
            res.append(que.front())
        return res

[gsw9818]

代码

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = collections.deque() # 本质就是单调队列
        ans = []
        for i in range(len(nums)):
            while q and nums[q[-1]] <= nums[i]: q.pop() # 维持单调性
            while q and i - q[0] >= k: q.popleft() # 移除失效元素
            q.append(i)
            if i >= k - 1: ans.append(nums[q[0]])
        return ans

[paopaohua]

思路

数组--->双端队列（移除 超出窗口范围的数索引大于 i - k + 1的元素 + 如果小于当前元素就出队列）

代码

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//创建滑动窗口个数的数组
int[] ans = new int[nums.length - k + 1];
//创建双端队列
Deque<Integer> deque = new ArrayDeque<>();

    for(int i = 0;i < nums.length;i++){

        if(!deque.isEmpty() && deque.peekFirst() + k <= i) deque.pollFirst();
        while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
            deque.pollLast();
        }
        deque.offerLast(i);//队列尾部添加元素
        if(i - k + 1 >= 0) ans[i-k+1] = nums[deque.peekFirst()];
    }
    return ans;
}

}

### 复杂度
- 时间：o(n)
- 空间：o(k)

[A-pricity]

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    let res = [];
    let que = []; // 队列最多容纳k个数
    for(let i = 0; i < nums.length; i++) {
        if(que.length === 0) que.push(nums[i]);
        else { // 维护队列
            // 出队列就两种情况
            // 1、 队头元素不在窗口（从队头出）
            // 2、 当前元素大于队尾元素（从队尾出）
            if(i - k >= 0 && nums[i - k] === que[0]) que.shift(); // 当队头元素出窗口时，弹出
            // 当前元素若大于队尾元素，则移出，直到遇到小于的元素或者队列空了，进队
            while(que.length > 0 && nums[i] > que[que.length - 1]){
                que.pop();
            }
            que.push(nums[i]);
        }
        // 当滑动完k个元素之后开始提取队头元素
        if(i >= k - 1) res.push(que[0]);
    }
    return res;
};

[zhuzhu096]

public int[] maxSlidingWindow(int[] nums, int k) { if (nums == null || nums.length == 0) return new int[0];

    int[] arr = new int[nums.length - k + 1];
    LinkedList<Integer> list = new LinkedList<>();

    for (int index = 0, i = 0; i < nums.length; i++) {
        while (!list.isEmpty() && nums[list.peekLast()] < nums[i]) {
            list.pollLast();
        }
        list.add(i);
        if (list.peek() == i - k) {
            list.poll();
        }
        if (i >= k - 1) {
            arr[index++] = nums[list.peek()];
        }
    }
    return arr;
}

[A-PolarBear]

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++){
            if (!deque.isEmpty() && deque.peekFirst() + k <= i) deque.pollFirst();
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
                deque.pollLast();
            }
            deque.offerLast(i);
            if (i - k + 1 >= 0) ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

[RestlessBreeze]

思路

优先队列

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

复杂度

时间：o(nlogn) 空间：o(n)

[Albert556]

class Solution { public: vector res; vector maxSlidingWindow(vector& nums, int k) { deque q; // 双端队列，存储的是当前窗口最大值的索引，维护操作: 保持单调递减，队头是最大值

    for (int i = 0; i < nums.size(); i++) {
        // 依次地将数组元素加入到队列中
        // 注意: 确保队列元素间的距离都在k以内
        if (!q.empty() && i - k + 1 > q.front()) /* 倒着数第k个与队列开头数的index比较。窗口长度>k时，从队列中删掉最前面的数 */
            q.pop_front();
        while (!q.empty() && nums[i] >= nums[q.back()])
            q.pop_back();  /* 不断地把左侧比自己小的数从队列中删掉, 遇到下一个比自己大的数时自己会被删掉。遇到比自己小的数得留着，最终双端队列会成为递减队列。 */

        q.push_back(i);
        if (i >= k - 1)      // 只要窗口大小 ≥ k 时, 窗口就会有最大值，将其放进res(结果vector)中
        {
            res.push_back(nums[q.front()]);
        }
    }

    return res;
}

};

[BruceZhang-utf-8]

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums.length<2){ return nums; } //双向队列，保存当前窗口的最大值，保证队列中的值从大到小排列 LinkedList queue = new LinkedList(); //结果 int[] res = new int[nums.length-k+1]; for(int i=0;i<nums.length;i++){ //队列中要保持从大到小排列，如果队尾的值小，则需要依次弹出 while(!queue.isEmpty()&&nums[queue.peekLast()]<=nums[i]){ queue.pollLast(); } //添加当前值进入队列 queue.addLast(i); //判断当前队列中队首的值是否有效 if(queue.peek()<=i-k){ queue.poll(); } //当窗口长度为k时，保存当前窗口的最大值 if(i+1>=k){ res[i+1-k]=nums[queue.peek()]; } } return res; } }

[GG925407590]

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < n; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k) {
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

[Elon-Lau]

class Solution { public: vector maxSlidingWindow(vector& nums, int k) { int n = nums.size(); deque q; for (int i = 0; i < k; ++i) { while (!q.empty() && nums[i] >= nums[q.back()]) { q.pop_back(); } q.push_back(i); }

    vector<int> ans = {nums[q.front()]};
    for (int i = k; i < n; ++i) {
        while (!q.empty() && nums[i] >= nums[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
        while (q.front() <= i - k) {
            q.pop_front();
        }
        ans.push_back(nums[q.front()]);
    }
    return ans;
}

};

[KyleYangSde]

var maxSlidingWindow = function(nums, k) { const queue = [], result = [] for (let i = 0; i < nums.length; i++) { // 如果队列不为空，且要入队的元素大于队尾元素, 队尾元素出队 while (queue.length > 0 && nums[i] > nums[queue[queue.length - 1]]) { queue.pop() } queue.push(i)

    // j 是把 i 为作为滑动窗口最后一个值时滑动窗口第一个值的索引
    const j = i - k + 1
    // j >= 0 说明滑动窗口已构建完毕
    if (j >= 0) {
        // 当队首元素不属于当前滑动窗口时出队
        if (queue[0] < j) queue.shift()
        // 把队首元素添加到结果数组中
        result.push(nums[queue[0]])
    }
}
return result

};

[liuajingliu]

代码实现

var maxSlidingWindow = function(nums, k) { const n = nums.length; const q = []; for (let i = 0; i < k; i++) { while (q.length && nums[i] >= nums[q[q.length - 1]]) { q.pop(); } q.push(i); }

const ans = [nums[q[0]]];
for (let i = k; i < n; i++) {
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
        q.pop();
    }
    q.push(i);
    while (q[0] <= i - k) {
        q.shift();
    }
    ans.push(nums[q[0]]);
}
return ans;

};

复杂度分析

• 时间复杂度：$O(N)$

• 空间复杂度 $O(N)$，即为存储 prefixMax和suffixMax 需要的空间

[xuanaxuan]

思路

双端队列

用一个双端队列来保存接下来的滑动窗口可能成为最大值的数

具体做法：

• 入队列
• 移除失效元素，失效元素有两种

1. 一种是已经超出窗口范围了，比如我遍历到第 4 个元素，k = 3，那么 i = 0 的元素就不应该出现在双端队列中了。具体就是索引大于 i - k + 1的元素都应该被清除
2. 小于当前元素都没有利用价值了，具体就是从后往前遍历（双端队列是一个递减队列）双端队列，如果小于当前元素就出队列

经过上面的分析，不难知道双端队列其实是一个递减的一个队列，因此队首的元素一定是最大的。

var maxSlidingWindow = function (nums, k) {
  const res = [];
  const dequeue = new Dequeue([]);
  // 前 k - 1 个数入队
  for (let i = 0; i < k - 1; i++) {
    dequeue.push(nums[i]);
  }

  // 滑动窗口
  for (let i = k - 1; i < nums.length; i++) {
    dequeue.push(nums[i]);
    res.push(dequeue.max());
    dequeue.shift(nums[i - k + 1]);
  }
  return res;
};

class Dequeue {
  constructor(nums) {
    this.list = nums;
  }

  push(val) {
    const nums = this.list;
    // 保证数据从队头到队尾递减
    while (nums[nums.length - 1] < val) {
      nums.pop();
    }
    nums.push(val);
  }

  // 队头出队
  shift(val) {
    let nums = this.list;
    if (nums[0] === val) {
      // 这里的js实现shift()理论上复杂度应该是O(k), 就不去真实实现一个O(1)出队的队列了，意思到位即可
      nums.shift();
    }
  }

  max() {
    return this.list[0];
  }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(k)

[wtdcai]

代码

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)

        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heapq.heappop(q)
            ans.append(-q[0][0])

        return ans

[tzuikuo]

思路

滑动窗口，双指针

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> maxqueue;
        int n=nums.size();
        vector<int> results;
        for(int i=0;i<k;i++){
            if(maxqueue.empty()) maxqueue.push_back(nums[i]);
            else{
                while(!maxqueue.empty()&&maxqueue.back()<nums[i]) maxqueue.pop_back();
                maxqueue.push_back(nums[i]);
            }
        }

        for(int i=0;i<n-k;i++){
            results.push_back(maxqueue.front());
            //cout<<"i="<<i<<" "<<maxqueue.front()<<" ";
            if(nums[i]==maxqueue.front()){
                maxqueue.pop_front();
            }
            if(maxqueue.empty()) maxqueue.push_back(nums[i+k]);
            else{
                while(!maxqueue.empty()&&maxqueue.back()<nums[i+k]) maxqueue.pop_back();
                maxqueue.push_back(nums[i+k]);
                //cout<<"i="<<i<<" "<<nums[i+k]<<" "<<endl;
            }
            //results.push_back(maxqueue.front());
        }
        results.push_back(maxqueue.front());
        return results;
    }
};

复杂度分析

• 时间复杂度：O(N)。
• 空间复杂度：O(k)

[MaylingLin]

思路

用双端队列保存滑动窗口最大值，移除失效元素

代码

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q, res = [], []
        for i, num in enumerate(nums):
            while q and q[-1][1] < num:
                q.pop()
            q.append((i, num))
            while i - q[0][0] >= k:
                q.pop(0)
            if i >= k-1:
                res.append(q[0][1])
        return res

复杂度

• Time: $O(n)$，n为数组长度
• Space: $O(k)$

[AtaraxyAdong]

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

[sclihuiming]

func maxSlidingWindow(nums []int, k int) []int {
    if k > len(nums) {
        return nil
    }

    slipArr := []int{}
    push := func(i int) {
        for len(slipArr) > 0 && nums[i] >= nums[slipArr[len(slipArr)-1]] {
            slipArr = slipArr[:len(slipArr)-1]
        }
        slipArr = append(slipArr, i)
    }
    for index := 0; index < k; index++ {
        push(index)
    }

    res := []int{nums[slipArr[0]]}

    for index := k; index < len(nums); index++ {
        push(index)
        for slipArr[0] <= index-k {
            slipArr = slipArr[1:]
        }
        res = append(res, nums[slipArr[0]])
    }
    return res
}

[Jetery]

239. 滑动窗口最大值

思路

维护一个单调队列, 每次滑动窗口时添加队头元素

代码 (cpp)

class Solution {
private:
    class MyQueue {
    public:
        deque<int> q; 
        void pop(int value) {
            if (!q.empty() && value == q.front()) {
                q.pop_front();
            }
        }

        void push(int value) {
            while (!q.empty() && value > q.back()) {
                q.pop_back();
            }
            q.push_back(value);

        }

        int front() {
            return q.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue q;
        vector<int> result;
        for (int i = 0; i < k; i++) {
            q.push(nums[i]);
        }
        result.push_back(q.front()); 
        for (int i = k; i < nums.size(); i++) {
            q.pop(nums[i - k]); 
            q.push(nums[i]); 
            result.push_back(q.front());
        }
        return result;
    }
};

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(n)

[Alexno1no2]

copy
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or not k:
            return []
        if len(nums) == 1:
            return [nums[0]]

        # 初始化队列和结果，队列存储数组的下标
        queue = []
        res = []

        for i in range(len(nums)):
            # 如果当前队列最左侧存储的下标等于 i-k 的值，代表目前队列已满，新元素需要进来，列表最左侧的下标出队列
            if queue and queue[0] == i - k:
                queue.pop(0)

            # 对于新进入的元素，如果队列前面的数比它小，那么前面的都出队列
            while queue and nums[queue[-1]] < nums[i]:
                queue.pop()
            # 新元素入队列
            queue.append(i)

            # 当前的大值加入到结果数组中
            if i >= k-1:
                res.append(nums[queue[0]])

        return res

[neado]

思路

双端队列

• 维护队列大小

• 索引大于 i - k + 1,出队

• 小于当前元素，出队

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len=nums.length;
        int[] res = new int[len - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < len; i++){
            //索引大于 i - k + 1,出队
            if (!dq.isEmpty() && dq.peekFirst() + k <= i) {
                dq.pollFirst();
            }
            //小于当前元素，出队
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]){
                dq.pollLast();
            }
            dq.offerLast(i);
            if (i - k + 1 >= 0) {
                res[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return res;
    }
}

算法复杂度

TIME:O(n) SPACE:O(k)

[zhiyuanpeng]

import heapq
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        h, ans = [], []
        for i in range(k):
            heapq.heappush(h, (-nums[i], i))
        ans.append(-h[0][0])
        for i in range(k, len(nums)):
            heapq.heappush(h, (-nums[i], i))
            while h[0][1] < i-k+1:
                heapq.heappop(h)
            ans.append(-h[0][0])
        return ans

time O(NlogK) space O(k)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        s = collections.deque()
        ans = []
        for i in range(len(nums)):
            while s and nums[s[-1]] <= nums[i]:
                s.pop()
            while s and i-s[0] >= k:
                s.popleft()
            s.append(i)
            if i >= k-1:
                ans.append(nums[s[0]])
        return ans

time O(N) space O(K)