一、前言

力扣239.滑動窗口最大值

滑動窗口最大值，這道題給定一個數組，以及一個窗口的長度，這個窗口會往后滑動，直到數組最后一個元素。

要求每個滑動窗口的中的最大值。對于這道題，我剛看到的時候沒有比較好的思路，心里想沒思路？直接一個無腦暴力！

暴力的思路就是遍歷數組的時候，每次遍歷滑動窗口找出最大值！

果然，超時了。。。。。。

遍歷數組的時間復雜度是O(n)，如果當滑動窗口的長度為n/2的時候，遍歷滑動窗口找出最大值的時間復雜度是O(n)，那么整體的暴力算法的時間復雜度是O(n2)。

---

二、單調隊列

正所謂“空間換時間”，所以在這題中，想要降低時間復雜度，那就要犧牲一點空間，用空間來換時間。

這道題單看數組可能不是很直觀，如果將數組轉化為折線圖，那么就能看出規則了！

假設現在有一個這樣的數組，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了

整體思路如上所示，這里需要用到一個數據結構——單調隊列，思路如下：

1. 入隊列，將元素添加到隊尾，并且需要維持隊列的單調性（隊列從大到小排序）
2. 出隊列，當元素超出滑動窗口的范圍的時候，需要出隊列
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;
}

解決！下班！！！

---