2._最大滑动窗口

• 2.25

  • 先试着添加新人，删除位置给新人留位置

  • 在判断是否窗口已满，删除first 位置

  • 根据当前位置是否窗口是否成型，来加入结果到 res 中

  • list 中时从队首到队尾单调递减的

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        int[] res = new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            while(!list.isEmpty()&&nums[list.peekLast()]<nums[i]){
                list.removeLast();
            }
            list.addLast(i);
            if(list.peekFirst()<i-k+1){
                list.removeFirst();
            }
            if(i>=k-1){
                res[i-k+1] = nums[list.peekFirst()];
            }
        }
        return res;
    }
}

• 2.6
  • 比较新老旧人的时候，比较的是值而不是下标，但是双端队列存的是下标哦
  • 注意好窗口和一个窗口的值，想好大于小于

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<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.peekLast()]<nums[i]){
                deque.removeLast();
            }
            deque.addLast(i);
            if(deque.peekFirst()<i-k+1){
                deque.removeFirst();
            }
            if(i>=k-1){
                res[i-k+1] = nums[deque.peekFirst()];
            }
        }
 
        return res;
    }
}

• 1.23
  • 窗口范围 ： [i-k+1,i] （以 i 为锚点倒推）
  • 第一个窗口形成：k-1（下标从 0 开始）
  • 要年龄小还要能力高的
  • 还可以，用到双端队列

import java.util.LinkedList;
 
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
 
        int n = nums.length;
        int[] result = new int[n - k + 1]; // 存放结果的数组
        
        // 使用 LinkedList 作为双端队列
        // 队列里存的是【数组下标】，而不是数值！
        LinkedList<Integer> deque = new LinkedList<>();
 
        for (int i = 0; i < n; i++) {
            // 1. 【核心逻辑：保持单调递减】
            // 如果队列不为空，且当前遍历到的数字 nums[i] 大于等于队尾的数字
            // 说明队尾的那个数字没用了（被当前这个又新又强的数字碾压了），把它移除
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.removeLast(); // 移除队尾
            }
 
            // 2. 将当前元素的下标加入队尾
            deque.addLast(i);
 
            // 3. 【清理过期元素】
            // 检查队头元素（最大值）的下标是否已经滑出了窗口范围
            // 当前窗口范围是 [i - k + 1, i]，如果队头下标 <= i - k，说明过期了
            if (deque.peekFirst() < i - k + 1) {
                deque.removeFirst(); // 移除队头
            }
 
            // 4. 【记录结果】
            // 当窗口长度达到 k 时（也就是 i >= k - 1），开始记录最大值
            if (i >= k - 1) {
                // 队头元素始终是当前窗口内最大值的下标
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
 
        return result;
    }
}