[Vssue]0239.滑动窗口最大值.md

[youngyangyang04]

https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html

[LiWangTian]

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { ArrayDeque deque = new ArrayDeque<>(); int n = nums.length; int[] res = new int[n - k + 1]; int idx = 0; for(int i = 0; i < n; i++) { // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点 // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出 while(!deque.isEmpty() && deque.peek() < i - k + 1){ deque.poll(); }

        // 2. 移除队列中所有小于当前元素的元素，保持队列单调递减（我觉得比否则也弹出好理解多了。。。明明就是大于了移除后面还得加进队列弹出什么呢）
        while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        deque.offer(i);

        // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
        if(i >= k - 1){
            res[idx++] = nums[deque.peek()];
        }
    }
    return res;
}

}

[Du1in9]

class Solution {
    private class Myque {
        Deque<Integer> dq;

        public Myque() {
            dq = new ArrayDeque<>();
        }
        void pop(int x) {
            if (!dq.isEmpty() && x == dq.peekFirst()) {
                dq.pollFirst();
            }
        }
        void push(int x) {
            while (!dq.isEmpty() && x > dq.peekLast()) {
                dq.pollLast();
            }
            dq.offerLast(x);
        }
        int front() {
            return dq.peekFirst();
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        Myque q = new Myque();
        int n = nums.length, j = 0;
        int[] res = new int[n - k + 1];

        for (int i = 0; i < k; i++) {   // 1. 初始化窗口
            q.push(nums[i]);
        }
        res[j++] = q.front();
        for (int i = k; i < n; i++) {   // 2. 滑动窗口过程
            q.pop(nums[i - k]);
            q.push(nums[i]);
            res[j++] = q.front();
        }
        return res;
    }
}

[MusherM]

使用记录下标的优先级队列，需要弹出时去看栈顶的下标在不在范围内，不在范围内就持续弹出直至下标符合范围，复杂度上不是最优，但是能过🤣

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // 创建优先队列实例
  const maxHeap = new MaxPriorityQueue();
  for (let i = 0; i < k; i++) {
    maxHeap.enqueue([nums[i], i], nums[i]);
  }
  let ans = [];
  ans[0] = maxHeap.front().element[0];
  for (let i = k; i < nums.length; i++) {
    maxHeap.enqueue([nums[i], i], nums[i]);
    while (maxHeap.front().element[1] <= i - k) {
      maxHeap.dequeue();
    }
    ans[i - k + 1] = maxHeap.front().element[0];
  }
  return ans;
};