239. 滑動窗口最大值

解題思路

• 計算每一個滑動窗口的最大值 關(guān)鍵在于借助單調(diào)隊(duì)列實(shí)現(xiàn)窗口
• 對于單調(diào)隊(duì)列 尾部添加元素 頭部刪除元素
• 添加元素操作：從尾部開始循環(huán)對比 刪除比當(dāng)前元素小的元素
• 獲取最大值元素 直接獲取頭部元素
• 刪除元素操作 直接刪除頭部元素

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 借助單調(diào)隊(duì)列  計算每一個滑動窗口的最大值MonotonicQueue window = new MonotonicQueue();// 單調(diào)隊(duì)列窗口List<Integer> res = new ArrayList<>();for(int i = 0; i < nums.length; i++){if(i < k - 1){window.push(nums[i]);// 先把前面k- 1 個元素填滿}else{// 窗口開始向前面移動// 移入新的元素window.push(nums[i]);// 因?yàn)槭菃握{(diào)隊(duì)列  直接計算最大值res.add(window.max());// 移除最后的元素window.pop(nums[i - k + 1]);}}// 將List 類型轉(zhuǎn)換為int[] 數(shù)組 作為返回值int[] arr = new int[res.size()];for(int i = 0; i < res.size(); i++){arr[i] = res.get(i);}return arr;}// 單調(diào)隊(duì)列的實(shí)現(xiàn)  尾部添加元素   頭部刪除元素  那么頭部元素是最大值// 維護(hù)的單調(diào)隊(duì)列 是需要從尾部到頭部的元素 全部單調(diào)遞增class MonotonicQueue{// 使用雙鏈表 模擬隊(duì)列  支持頭部和尾部添加和刪除元素private LinkedList<Integer> maxq = new LinkedList<>();public void push(int n){// 尾部添加一個元素  需要維護(hù)單調(diào)隊(duì)列 從尾部到頭部 單調(diào)遞增的性質(zhì)// 從尾部開始 將前面小于她的元素 全部刪除掉  這樣維護(hù)的就是一個單調(diào)隊(duì)列while(!maxq.isEmpty() && maxq.getLast() < n){maxq.pollLast();// 刪除尾部元素}maxq.addLast(n);// 添加元素   尾部添加元素}// 計算最大元素 直接就是取出 頭部元素 因?yàn)轭^部元素最大public int max(){return maxq.getFirst();}// 頭部刪除元素public void pop(int n){if(n == maxq.getFirst()){maxq.pollFirst();}}}
}