文章目录
- 一、前言
- 二、单调队列
一、前言
力扣239.滑动窗口最大值
滑动窗口最大值，这道题给定一个数组，以及一个窗口的长度，这个窗口会往后滑动，直到数组最后一个元素。
要求每个滑动窗口的中的最大值。对于这道题，我刚看到的时候没有比较好的思路，心里想没思路？直接一个无脑暴力！
暴力的思路就是遍历数组的时候，每次遍历滑动窗口找出最大值！
果然，超时了。。。。。。
遍历数组的时间复杂度是O(n)，如果当滑动窗口的长度为n/2的时候，遍历滑动窗口找出最大值的时间复杂度是O(n)，那么整体的暴力算法的时间复杂度是O(n²)。
二、单调队列
正所谓“空间换时间”，所以在这题中，想要降低时间复杂度，那就要牺牲一点空间，用空间来换时间。
这道题单看数组可能不是很直观，如果将数组转化为折线图，那么就能看出规则了！
假设现在有一个这样的数组，nums = [2,1,4,2,3,2], k = 3，该数组的折线图如下所示。
在[2,1,4]这个滑动窗口里面，最大值的4，但是2和1有没有可能作为滑动窗口的最大值呢？
这个是不可能的，因为4在2和1的右边，包含了1或2的滑动窗口必然包含了4，因此4会是最大值，而2和1没有机会成为最大值，于是就需要记录4。
随着滑动窗口往下往下滑动，那么滑动窗口为[1,4,2]，最大值仍然为4，前面说了1是不可能有成为最大值的记录，那么这里的2有成为最大值的机会么？
很显然，是有可能的，因为2在4的右边，而且2后面的数字还不知道，有可能是比2小，并且在后面包含了2的滑动窗口中，可能不会包含4，因此2有可能成为最大值，于是需要将2记录下来。
窗口继续往下滑动，滑动窗口为[4,2,3]，最大值为4，由于这次有3，3比2大，和前面一样，有3在，2不可能成为最大值，于是移除前面记录的2，而是将3进行记录。
窗口继续滑动，滑动窗口为[2,3,2]，这时候4已经超出滑动窗口范围，需要在前面记录的数据中移除，于是这次滑动窗口的最大值就是3了
整体思路如上所示，这里需要用到一个数据结构——单调队列，思路如下：
- 入队列，将元素添加到队尾，并且需要维持队列的单调性（队列从大到小排序）
- 出队列，当元素超出滑动窗口的范围的时候，需要出队列
- 记录答案，每次滑动窗口的最大值就是队列的首部！
public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length - k + 1];Deque<Integer> queue = new LinkedList<>();for (int i = 0; i < nums.length; i++) {while (!queue.isEmpty() && nums[i] > nums[queue.getLast()]){// 维持单调性queue.removeLast();}if (!queue.isEmpty() && i - queue.getFirst() >= k){queue.removeFirst();}queue.addLast(i);if (i >= k - 1){// 收集结果res[i - k + 1] = nums[queue.getFirst()];}}return res;
}
解决！下班！！！