【Day 28 】2023-03-13 - 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

[airwalkers]

// 打卡

[JiangyanLiNEU]

• heap
• T = O(NlogN)
• S = O(N)

  class Solution:
  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
      res = []
      heap1 = []
      heapq.heapify(heap1)
      for i in range(len(nums)+1):
          if i>=k:
              found = False
              while not found:
                  [value, index] = heapq.heappop(heap1)
                  if index+k >= i:
                      res.append(value*(-1))
                      found = True
                      heapq.heappush(heap1, [value, index])
          i<len(nums) and heapq.heappush(heap1, [-1*nums[i], i])
      return res

• deque
• T = O(N)
• S = O(K)

  class Solution(object):
  def maxSlidingWindow(self, nums, k):
      window = deque()
      res = []
      for i in range(len(nums)):
          # remove the index that is out of the window
          while window and window[0] <= i-k:
              window.popleft()
          # the first element is always the index of greatest number in this window
          while window and nums[window[-1]] < nums[i]:
              window.pop()
          window.append(i)
          if i>=k-1:
              res.append(nums[window[0]])
      return res

[Yufanzh]

To do it in O(1), consider using a monotonic stack(decreasing stack) so that max value is at the top of queue.\n We use a deque data structure in python so that when we exceeding the sliding window size, we can do popleft()

import collections
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # monotonic stack -- decreasing stack, so max value is at top of queue
        mono = collections.deque()
        ans = []

        for i, num in enumerate(nums):
            while mono and nums[mono[-1]] <= num:
                mono.pop()
            mono.append(i)
            # when sliding window left, we pop the head of deque, that's why we stored the index
            if mono[0] == i - k:
                mono.popleft()
            # when window size == k, we start to record and append max value to results
            if i >= k - 1:
                ans.append(nums[mono[0]])
        return ans

[Zoeyzyzyzy]

class Solution {
    //Method1: PriorityQueue + Array with length 2;
    //Time Complexity: O(nlogn) in worst case, the array is monotonically increasing, put n elements in pq need n*logn time
    //Space Complexity: O(n) pq need n to store n elements.
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int[] res = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            pq.offer(new int[] { nums[i], i });
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            if (i + 1 >= k) {
                res[i - k + 1] = pq.peek()[0];
            }
        }
        return res;
    }

    //method2: monotonic queue, use deque as monotonic queue
    //reason to use monotonic queue: because deque can be removed from both head and tail.
    //Time Complexity: O(n), Space complexity: O(k);
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int n = nums.length;
        LinkedList<Integer> dequeue = new LinkedList<>();
        int[] res = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            dequeue.add(i);
            while (!dequeue.isEmpty() && nums[dequeue.peekLast()] <= nums[i]) {
                dequeue.removeLast();
            }
            dequeue.addLast(i);
            while (dequeue.peek() <= i - k) {
                dequeue.removeFirst();
            }
            if (i + 1 >= k) {
                res[i + 1 - k] = nums[dequeue.peek()];
            }

        }
        return res;
    }
    //method3:create a monotonic queue manually
        class MonotonicQueue {
            private LinkedList<Integer> maxq = new LinkedList<>();

            //删除所有小于n的元素
            public void push(int n) {
                while (!maxq.isEmpty() && maxq.getLast() < n) {
                    maxq.pollLast();
                }
                maxq.addLast(n);
            }

            public int max() {
                return maxq.getFirst();
            }

            public void pop(int n) {
                if (n == maxq.getFirst()) {
                    maxq.pollFirst();
                }
            }
        }

        public int[] maxSlidingWindow2(int[] nums, int k) {
            MonotonicQueue window = new MonotonicQueue();
            int n = nums.length;
            int[] res = new int[n + 1 - k];
            for (int i = 0; i < n; i++) {
                window.push(nums[i]);
                if (i >= k - 1) {
                    res[i - k + 1] = window.max();
                    window.pop(nums[i + 1 - k]);
                }
            }
            return res;
        }
}

[NorthSeacoder]

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    //单调递减队列,保存下标
    const queue = [];
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        while (queue.length && nums[i] >= nums[queue.at(-1)]) {
            //保持队列,单调递减
            //当入队元素大于队尾时,队尾元素出队(pop:移除数组最后一个元素)
            queue.pop();
        }
        //此时队尾元素大于当前待入队元素
        queue.push(i);
        //i-k:窗口前端下标
        //队首元素:当前队列最大值
        //判断队首元素是否在窗口内
        while (queue[0] <= i - k) {
            queue.shift();
        }
        //当 i>=k-1 时,i 遍历过 k 个元素
        //即此时以满足窗口大小
        if (i >= k - 1) res.push(nums[queue[0]]);
    }
    return res;
};

• TC: O(n)
• SC: O(k)

[xb798298436]

solution(nums, k) { const res = []; let array = nums.splice(0,k); let curMax = -Infinity; for (let i = 0; i < k; i++) { curMax = Math.max(array[i], curMax); } res.push(curMax); for (let i = 0; i < nums.length; i++) { if(nums[i]>curMax){ curMax = nums[i]; res.push(curMax) }else{ res.push(curMax) } } return res; },

[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;
    }
};

复杂度分析 待定

[ccslience]

import collections
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # monotonic stack -- decreasing stack, so max value is at top of queue
        mono = collections.deque()
        ans = []

        for i, num in enumerate(nums):
            while mono and nums[mono[-1]] <= num:
                mono.pop()
            mono.append(i)
            # when sliding window left, we pop the head of deque, that's why we stored the index
            if mono[0] == i - k:
                mono.popleft()
            # when window size == k, we start to record and append max value to results
            if i >= k - 1:
                ans.append(nums[mono[0]])
        return ans

[FlipN9]

/**
    维护一个 单调递减 的 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;
    }
}

[Elsa-zhang]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or not k:
            return None

        # 堆
        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

[954545647]

// 滑动窗口
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  let n = nums.length;
  class slideWindow {
    constructor() {
      this.data = [];
    }
    push(val) {
      let data = this.data;
      // 保证数据从队头到队尾递减
      while (data.length > 0 && data[data.length - 1] < val) {
        data.pop();
      }
      data.push(val);
    }
    pop(val) {
      let data = this.data;
      if (data.length > 0 && data[0] === val) {
        // 这里的js实现shift()理论上复杂度应该是O(k), 就不去真实实现一个O(1)出队的队列了，意思到位即可
        data.shift();
      }
    }
    max() {
      return this.data[0];
    }
  }
  let res = [];
  let windows = new slideWindow();
  debugger;
  for (let i = 0; i < n; i++) {
    if (i < k - 1) {
      windows.push(nums[i]);
    } else {
      windows.push(nums[i]);
      res.push(windows.max());
      windows.pop(nums[i - k + 1]);
    }
  }
  return res;
};

[linlizzz]

思路

只会用暴力算法，没通过，看了答案和官方题解的解析，知道了要用双指针加队列维持一个单调递减队列，保证移动过程中超过长度k的前序元素移除，并且小于新进元素的失效元素移除

代码

示例代码

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

复杂度分析

T(n) = O(n)

S(n) = O(k)

[airwalkers]

// 思路，单调递减栈，栈底即最大值，同时维持栈的深度不能超过k，超过则去栈底
// nums = [1,3,-1,-3,5,3,6,7], k = 3
//         滑动窗口的位置                最大值     单调栈
//        ---------------               -----
//        [1  3  -1] -3  5  3  6  7       3     3,-1
//         1 [3  -1  -3] 5  3  6  7       3     3,-3,-3             
//         1  3 [-1  -3  5] 3  6  7       5     5
//         1  3  -1 [-3  5  3] 6  7       5     5,3
//         1  3  -1  -3 [5  3  6] 7       6     6
//         1  3  -1  -3  5 [3  6  7]      7     7

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[deque.peek()] < nums[i]) {
                deque.pop();
            }
            while (!deque.isEmpty() && i - deque.getLast() >= k) {
                deque.removeLast();
            }

            deque.push(i);
            if (i - k + 1 >= 0) {
                res[i - k + 1] = nums[deque.getLast()];
            }
        }
        return res;
    }
}

[chanceyliu]

代码

function maxSlidingWindow(nums: number[], k: number): number[] {
  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)

[SoSo1105]

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

[snmyj]

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans={};
        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);
        }
        ans.push_back(nums[q.front()]);
        for(int i=k;i<nums.size();i++){
           while(!q.empty()&&nums[i]>nums[q.back()]) q.pop_back();
           q.push_back(i);
           while(i-q.front()>=k) q.pop_front();
           ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

[kofzhang]

思路

双端队列，当前值大于队列前面值，把前面的弹出，把当前值放进去。 当队首失效，也就是失效值=队首值，队首出队。 当index大于k的时候，队首为最大值，把队首扔进res。

复杂度

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

代码

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        cur = 0
        q  = deque()
        res = []        
        while cur<len(nums):
            while q and  nums[cur]>q[-1]:
                q.pop()
            q.append(nums[cur])
            if cur>=k and nums[cur-k]==q[0]:
                q.popleft()
            if cur>=k-1:    
                res.append(q[0])
            cur += 1
        return res

[jackgaoyuan]

type Node struct {
    Value int
    Next *Node
    Prev *Node
}

type Deque struct {
    Head *Node
    Tail *Node
    Count int
}

func CreateDeque () Deque {
    head := &Node{}
    tail := &Node{}
    head.Next = tail
    tail.Prev = head
    return Deque{ Head: head, Tail: tail, Count: 0 }
}

func (dq *Deque) InsertHead(value int) {
    node := &Node{ Value: value }
    node.Prev, node.Next = dq.Head, dq.Head.Next
    node.Prev.Next, node.Next.Prev = node, node
    dq.Count += 1
}

func (dq *Deque) DeleteHead() {
    firstNode := dq.Head.Next
    firstNode.Prev.Next, firstNode.Next.Prev = firstNode.Next, firstNode.Prev
    firstNode.Next, firstNode.Prev = nil, nil
    dq.Count -= 1
}

func (dq *Deque) InsertTail(value int) {
    node := &Node{ Value: value }
    node.Prev, node.Next = dq.Tail.Prev, dq.Tail
    node.Prev.Next, node.Next.Prev = node, node
    dq.Count += 1
}

func (dq *Deque) DeleteTail() {
    lastNode := dq.Tail.Prev
    lastNode.Prev.Next, lastNode.Next.Prev = lastNode.Next, lastNode.Prev
    lastNode.Prev, lastNode.Next = nil, nil
    dq.Count -= 1
}

func (dq *Deque) PeerHead() int {
    return dq.Head.Next.Value
}

func (dq *Deque) PeerTail() int {
    return dq.Tail.Prev.Value
}

func maxSlidingWindow(nums []int, k int) []int {
    dq := CreateDeque()
    res := []int{}
    for idx, value := range nums {
        for dq.Count > 0 && nums[dq.PeerTail()] < value {
            dq.DeleteTail()
        }
        dq.InsertTail(idx)
        if idx >= k - 1 {
            for dq.Count > 0 && dq.PeerHead() < idx - k + 1 {
                dq.DeleteHead()
            }
            res = append(res, nums[dq.PeerHead()])
        }
    }
    return res
}

[Abby-xu]

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

[GuitarYs]

···python class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: cur = 0 q = deque() res = []
while cur<len(nums): while q and nums[cur]>q[-1]: q.pop() q.append(nums[cur]) if cur>=k and nums[cur-k]==q[0]: q.popleft() if cur>=k-1:
res.append(q[0]) cur += 1 return res

[Quieter2018]

思路 见下述代码释义。

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        //双向队列
        deque<int> dq;
        for (int i = 0; i < nums.size(); ++i) {
            //如果窗口长度超过了k，则将最左边的元素移除
            if (!dq.empty() && dq.front() == i - k) 
                dq.pop_front();

            //从后往前移除所有队列中小于当前元素的元素
            while (!dq.empty() && nums[i] > nums[dq.back()]) 
                dq.pop_back();

            //在队列中添加当前元素的坐标
            dq.push_back(i);

            //如果窗口长度已经到达了k，则在结果中插入最大值(deque最前面的元素)
            if (i >= k-1) 
                result.push_back(nums[dq.front()]);
        }
        return result;
    }
};

复杂度分析 时间复杂度：O(n) 空间复杂度：O(n)

[duke-github]

思路

优先队列的优化 值-下标的二元组加入到序列中 加入的过程中，从队尾删除值和下标均小于当前二元组的元素 
向右滑动窗口 序列的第一个元素即为该下标的答案 当头二元组的下标和当前下标相同时 从序列中删除头

复杂度

每个二元组至多入队列一次出队列一次 时间复杂度O(n) 空间复杂度O(n)

代码

class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        //序列记录  值 - 下标
        LinkedList<int[]> valueList = new LinkedList<>();
        //将前n个加入到序列中
        for (int i = 0; i < k; i++) {
            addToList(new int[]{nums[i], i}, valueList);
        }
        int[] ans = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length - k; i++) {
            ans[i] = valueList.getFirst()[0];
            addToList(new int[]{nums[i + k], i + k}, valueList);
            if (valueList.getFirst()[1] <= i) {
                valueList.removeFirst();
            }
        }
        ans[ans.length - 1] = valueList.getFirst()[0];
        return ans;
    }

    private static void addToList(int[] value, LinkedList<int[]> valueList) {
        while (valueList.size() > 0 && value[0] >= valueList.getLast()[0]) {
            valueList.removeLast();
        }
        valueList.addLast(value);
    }
}

[harperz24]

• max heap

  class Solution:
  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
      maxheap = [(-nums[i], i) for i in range(k)]
      heapq.heapify(maxheap)
  
      res = []
      res.append(-maxheap[0][0])
  
      for i in range(k, len(nums)):
          heapq.heappush(maxheap, (-nums[i], i))
  
          while i - maxheap[0][1] >= k:
              heapq.heappop(maxheap)
          res.append(-maxheap[0][0])
  
      return res
  
      # max heap
      # time: O(n * logn)
      # space: O(n)

• mono deque

  class Solution:
  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
      deque = collections.deque()
      for i in range(k):
          while deque and nums[i] >= deque[-1][0]:
              deque.pop()
          deque.append((nums[i], i))
  
      res = []
      res.append(deque[0][0])
  
      for i in range(k, len(nums)):
          while deque and nums[i] >= deque[-1][0]:
              deque.pop()
          deque.append((nums[i], i))
  
          while i - deque[0][1] >= k:
              deque.popleft()
          res.append(deque[0][0])
  
      return res
  
      # desending mono-deque
      # time: O(n)
      # space: O(n)

[jmaStella]

思路

monotonic decreasing deque 存的是index of num 如果 deque头 的index 不再窗口里面, pollFIrst 如果 deque尾 的index 的值 < nums[i], pollLast 把deque头的值放进result里面

代码

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

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

            if(i+1 -k >=0){
                result[i+1-k]  = nums[deque.peekFirst()];
            }
        }
        return result;

    }

复杂度

时间O(N) 空间O(N)

[FireHaoSky]

思路：

""" 方法一：优先队列，队列中保存数值和下标，当下标在范围内，队列头即为最大值；否则就弹出队列头；
方法二：单调队列，在优先队列的方法基础上，先保存前k个范围的最大值，及其后面的值，队列中保存其下标；
然后遍历，小于最后值的直接保存；大于的，弹出队列末尾，知道符合条件，然后检测队列头的下标是否符合，否则弹出，保存当前最大值。 """

代码：python

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque()
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)

        ans = [nums[q[0]]]
        for i in range(k,n):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            while q[0] <= i-k:
                q.popleft()
            ans.append(nums[q[0]])
        return ans

复杂度分析：

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

[Fuku-L]

思路

优先队列 使用优先队列做大顶堆，在加入一个元素的之后，需要将窗口最左侧的值出队。 因此队列需要使用 int[] 作为类型，保存遍历的下标和值。具体步骤在代码中。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 1. 将 nums 的前k个元素放入优先队列中
        int n = nums.length;
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] pair1, int[] pair2){
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair2[1];
            }
        });
        for(int i = 0; i<k; i++){
            queue.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = queue.peek()[0];
        // 2. 向右移动时，将一个元素入队，此时堆顶为最大值
        for(int i = k; i<nums.length; i++){
            queue.offer(new int[]{nums[i], i});
            // 3. 将最左侧的值出队
            while(queue.peek()[1] <= i - k){
                queue.poll();
            }
            // 将堆顶保存
            ans[i - k + 1] = queue.peek()[0];
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[chocolate-emperor]

考察单调队列+滑动窗口。
维护一个单调递减的队列，每次新元素入队，都要从队尾去除比该元素小的值。队首保持最大值。
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(k==1 || nums.size()==1)  return vector<int>(nums);
        int l = nums.size();
        //
        vector<int> res;
        deque<int>window;

        int start = 0, end = 0;
        while(end<l){
            //  收缩
            if(end-start+1>k)   {
                if(nums[start]==window.front())     window.pop_front();
                start+=1;
            }
            //扩张
            while(!window.empty() 
                && window.back()<nums[end])   {window.pop_back();}
            window.push_back(nums[end]);
            //结算  
            if(end-start+1 == k)    res.emplace_back(window.front());
            end+=1;
        }
        return res;

    }
};

[zpbc007]

思路

用队列维护当前窗口中的最大值 初始化：遍历前 k 个元素，如果当前元素比队尾元素大，则删除队尾元素，直至队列为空或者当前元素小于等于队尾元素 移动窗口: 从 k 开始遍历数组：

1. 如果当前元素比队尾元素大，则删除队尾元素，直至队列为空或者当前元素小于等于队尾元素
2. 当前 index 添加到队列中
3. 如果队首 p[] <= index -k，则删除队首，直至不满足条件
4. 当前窗口最大值为队首对应的值

代码

function maxSlidingWindow(nums: number[], k: number): number[] {
    const queue: number[] = []

    // 初始化窗口
    for (let i = 0; i < k; i++) {
        while (queue.length && nums[i] > nums[queue[queue.length - 1]]) {
            queue.pop()
        }

        queue.push(i)
    }

    const ans: number[] = [nums[queue[0]]]

    for (let i = k; i < nums.length; i++) {
        while (queue.length && nums[i] > nums[queue[queue.length - 1]]) {
            queue.pop()
        }

        queue.push(i)

        // 窗口的左边界在 i - k - 1，右边界在 i
        while (queue[0] <= i - k) {
            queue.shift()
        }

        ans.push(nums[queue[0]])
    }

    return ans
}

复杂度

• 时间复杂度：O(N) 每个元素被添加到队列一次，最多移出一次
• 空间复杂度：O(K) 最多保存窗口 K 个元素

[JasonQiu]

• Deque

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

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

[jiujingxukong]

解题思路

问题其实就是维护一个滑动窗口，每次获取滑动窗口最大值即可。

暴力解法

获取固定长度为k的窗口中最大的值时，线性枚举 i 到 i + k 的值找出最大的

单调队列

我们没必须存储窗口内的所有元素。 如果新进入的元素比前面的大，那么前面的元素就不再有利用价值，可以直接移除。这提示我们使用一个单调递增栈来完成。但由于窗口每次向右移动的时候，位于窗口最左侧的元素是需要被擦除的，而栈只能在一端进行操作。而如果你使用普通的数组实现，就是可以在另一端操作了，但是时间复杂度仍然是 O(k)(实际使用普通的数组实现算法用时比暴力解法少，因为时间复杂度算的是最坏情况)，和上面的暴力算法时间复杂度一样。因此，我们考虑使用链表来实现，维护两个指针分别指向头部和尾部即可，这样做的时间复杂度是 O(1)，这就是双端队列（dequeue）。
因此思路就是用一个双端队列来保存接下来的滑动窗口可能成为最大值的数。 具体做法：

1. 入队列
2. 移除失效元素，失效元素有两种

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

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

解题代码

暴力法（时间超出限制）

var maxSlidingWindow = function (nums, k) {
  const res = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let cur = maxInSlidingWindow(nums, i, i + k);
    res.push(cur);
  }
  return res;
};

function maxInSlidingWindow(nums, start, end) {
  let max = -Infinity;
  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) {
      // 这里的js实现shift()理论上复杂度应该是O(k), 就不去真实实现一个O(1)出队的队列了，意思到位即可
      nums.shift();
    }
  }

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

复杂度分析

n为数组nums长度，k为滑动窗口长度 时间复杂度：O（n*k），由于这里双向队列是用数组实现的，所以还是乘以k 空间复杂度：O（k）

[Hughlin07]

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] res = 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() && deque.peekLast() <= nums[i]){
            deque.pollLast();
        }
        deque.offerLast(i);
        if(i-k+1 >= 0){
            res[i-k+1] = nums[deque.peekFirst()];
        }
    }
    return res;
}

}

Time: O(n)

Space: O(k)

[Meisgithub]

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

[zcytm3000]

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

[wangqianqian202301]

思路

用一个list , 0位置放最大值， 最右面放k个数之内可能的最大值。 每滑动一个值 ， 和右面的数比较 ， 比右面的数大， 就弹出 0位置的数，根据当前坐标， 滑动过去， 就弹出， 弹出后， 如果数组内还有元素， 则最左边（0位置）就是最大数。 如果没有了， 那当前数就是最大数。

代码

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

        for i in range(len(nums)):
            while dq and dq[0] <= i - k:
                dq.pop(0)
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()
            dq.append(i)
            if i >= k - 1:
                res.append(nums[dq[0]])

        return res

O(n)

[wangzh0114]

代码

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;
    }
};

---

复杂度分析

• TC:O(nlogn)
• SC:O(n)

[xiaoq777]

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];
        for(int i = 0; i < nums.length; i++) {
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            if(!deque.isEmpty() && i - deque.peek() >= k) {
                deque.poll();
            }
            deque.offer(i);
            if(i >= k-1) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }
        return result;
    }
}

[lp1506947671]

代码

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

复杂度分析

令 n 为数组长度

• 时间复杂度: O(n * k)
• 空间复杂度: O(1)

[AstrKing]

思路

单调队列，自己没想到用到堆的方法，这个后面再消化一下

代码

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(n)

[kangliqi1]

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

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

}

[RestlessBreeze]

code

class Solution {
public:

    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        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> res = {nums[q.front()]};
        int L = 1;
        for (int i = k; i < nums.size(); i++, L++)
        {
            while (!q.empty() && nums[i] > nums[q.back()])
                q.pop_back();         
            q.push_back(i);
            while (!q.empty() && q.front() < L)
                q.pop_front();
            res.push_back(nums[q.front()]);
        }
        return res;
    }
};

[bookyue]

TC: O(n)
SC: O(k)

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

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

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

            deque.addLast(i);

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

        return res;
    }

[Lrwhc]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if k == 0: return []
        res = []
        for r in range(k, len(nums) + 1):
            res.append(max(nums[r - k: r]))
        return res

[Lydia61]

239. 滑动窗口最大值

思路

优先队列

代码

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;
    }
};

复杂度分析

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

[X1AOX1A]

0239. 滑动窗口最大值

题目

给你一个整数数组 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]

思路

• 使用 MaxHeap 来维护窗口内的元素
• 当窗口移动时添加滑动窗口后一个数
  • 在 push 的时候加入 index 信息（(nums[i], i)），用于筛选窗口内的最大值
• 在返回栈顶元素（最大值）之前，删除不在窗口内的栈顶元素

注意点

• python 中的 heapq 为 MinHeap，因此在入栈以及出栈时需要加符号，以变为 MaxHeap
• 在入栈时增加 index 信息（(nums[i], i)），用于筛选窗口内的最大值

代码

import heapq
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max_heap=[]
        ans=[]

        # heapq 默认为 min heap，因此需要取负号变为 max heap
        for i in range(k):
            heapq.heappush(max_heap,(-nums[i],i))
        # 栈顶（max_heap[0]）为最大元素
        ans.append(-max_heap[0][0])

        for i in range(k,len(nums)):
            # 删除out date的数据，保证栈顶元素落入窗口内
            while max_heap and max_heap[0][1]<i-k+1:
                heapq.heappop(max_heap)
            # 加入新元素
            heapq.heappush(max_heap,(-nums[i],i))
            # 栈顶（max_heap[0]）为最大元素
            ans.append((-max_heap[0][0]))
        return ans

• 时间复杂度：O(n*logK)：insert 复杂度 O(logK)
• 空间复杂度：O(K)

[JingYuZhou123]

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  let res = [];
  let maxQ = [];
  for (let i = 0; i < k; i++) {
    const num = nums[i];
    while (maxQ.length && nums[maxQ[maxQ.length - 1]] <= num) {
      maxQ.pop();
    }
    maxQ.push(i);
  }
  res.push(nums[maxQ[0]]);
  for (let i = k; i < nums.length; i++) {
    const num = nums[i];
    if (maxQ.length && i - k + 1 > maxQ[0]) {
      maxQ.shift();
    }
    while (maxQ.length && nums[maxQ[maxQ.length - 1]] <= num) {
      maxQ.pop();
    }
    maxQ.push(i);
    res.push(nums[maxQ[0]]);
  }
  return res;
};

[ZhuMengCheng]

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
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

};

[joemonkeylee]

思路

自己做的超时了 看了题解也没做出来

用linkedlist实现双端队列 使得 队首元素 维持队列最大值

代码

        public int[] MaxSlidingWindow(int[] nums, int k)
        {
            int n = nums.Length;
            int[] res = new int[n - k + 1];
            LinkedList<int> dq = new LinkedList<int>();
            for (int i = 0; i < n; i++)
            {
                if (dq.Count != 0 && dq.First.Value < (i - k + 1))
                {
                    dq.RemoveFirst();
                }
                while (dq.Count != 0 && nums[i] >= nums[dq.Last.Value])
                {
                    dq.RemoveLast();
                }
                dq.AddLast(i);
                if (i >= k - 1)
                {
                    res[i - k + 1] = nums[dq.First.Value];
                }
            }
            return res;
        }

复杂度分析

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

[Jetery]

class Solution {

private:
    class MyQueue {
        public:
        deque<int> q;
        void push(int val) {
            while (!q.empty() && q.back() < val) 
                q.pop_back();
            q.push_back(val);
        }
        void pop(int val) {
            if (!q.empty() && q.front() == val) 
                q.pop_front();
        }
        int front() {
            return q.front();
        }
    };

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

[DragonFCL]

var maxSlidingWindow = function(nums, k) {
   const deque=[];
   const  result=[]; 
   for(let i=0;i<nums.length;i++){
     if(i-deque[0]>=k) deque.shift();
     while(nums[deque[deque.length-1]]<=nums[i]){
         deque.pop(); 
     }
     deque.push(i);
     if(i>=k-1) {  
         result.push(nums[deque[0]]);
     }
   }
   return result;
};

[for123s]

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size(), top;
        vector<int> left(n), right(n), res;
        for(int i=0;i<n;++i)
        {
            if(i%k==0)
            {    
                left[i] = nums[i];
                top = i+k-1>=n-1?n-1:i+k-1;
                right[top] = nums[top];
            }
            else
            {    
                left[i] = max(left[i-1],nums[i]);
                right[top-1] = max(nums[top-1],right[top]);
                --top;
            }
        }
        for(int i=0;i<n-k+1;++i)    
            res.emplace_back(max(left[i + k - 1], right[i]));
        return res;
    }
};