题解 | #滑动窗口最小值#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param k int整型
     * @return int整型一维数组
     */
  /**
  方法一:双向队列（链表） 时间复杂度O(n) 数学模拟居多 妙！！！
  */
    public int[] minSlidingWindow(int[] nums, int k) {
        // deque存放的是元素的索引值，而不是元素！！！
        Deque<Integer> deque = new LinkedList<>();
        int [] result = new int[nums.length - k + 1];
        // 结果数组的索引
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            // 移除已经不在窗口内的元素
            if ((!deque.isEmpty()) && (deque.peekFirst() < i - k + 1)) {
                // peekFirst是返回队首元素，但不删除，pollFirst是要做删除操作
                deque.pollFirst();
            }
            // 移除窗口内比当前元素还要大的元素，因为肯定不是最小值，从队尾开始移除,保持元素的递增顺序
            while ((!deque.isEmpty()) && (nums[deque.peekLast()] > nums[i])) {
                deque.pollLast();
            }
            // 将当前元素索引添加到队尾
            deque.offerLast(i);
            // 如果窗口长度已经到达k-1,说明可以找最小值了,比如i=2,k=3
            if (i >= k - 1) {
                if (!deque.isEmpty()) {
                    // 防止deque.peekFirst出现空指针异常
                    result[index++] = nums[deque.peekFirst()];
                }
            }
        }
        return result;
    }
  /**
  方法二：优先级队列 时间复杂度O(nlogk) k是堆的节点数 也就是窗口大小 比暴力解法还是好不少
  */
	public int[] minSlidingWindow(int[] nums, int k) {
		  // 优先级队列 (小根堆，保存最小值)
		  PriorityQueue<Integer> queue = new PriorityQueue<>();
		  // 窗口左边界
		  int left = 0;
		  // 窗口右边界
		  int right = 0;
		  // 结果数组索引
		  int index = 0;
		  // 初始化操作
		  while (right < k) {
			  queue.add(nums[right++]);
		  }
		  int[] result = new int[nums.length - k + 1];
		  // 初始化第一个最小值
		  if (!queue.isEmpty()) {
			  result[index++] = queue.peek();
		  }
		  // 当右边界小于数组长度时
		  while (right < nums.length) {
			  // 窗口向右移动 先删除左边界的元素
			  queue.remove(nums[left]);
			  // 左边界扩张
			  left++;
			  // 添加新的右边界元素
			  queue.add(nums[right]);
			  // 右边界扩张
			  right++;
			  // 拿取此时小根堆的顶部元素
			  if (!queue.isEmpty()) {
				  result[index++] = queue.peek();
			  }
		  }
		  return result;
	  }
}

本题知识点分析：

1.双向队列(链表)单调

2.优先级队列(小根堆，可以自定义，new Comparator就可以，建议Lambda表达式简写,(o1,o2)->(o2-o1)即可

3.数学模拟

4.队列存取

本题解题思路分析：

1.双向队列是方法一，数学模拟的思想居多，存储索引值，然后保持队列的递增特性，每次取出队首

2.优先级队列数学模拟就比较简单，缩减和扩展，小根堆内部排序，不用自己操作，唯一就是时间复杂度增加了

3.其他细节看注释就可以了，非常详细

本题使用编程语言: Java

建议大家还是多掌握几种做题的解法，暴力能不用就不用，因为面试的时候基本都是有要求的，暴力做出来大多数也是无用功，多用数据结构、常见API、算法类型、剪枝优化。

如果本篇文章对你有帮助的话，可以点个赞，有问题可以评论区留言，感谢支持~