## 雙端隊列 / Deque  ### 特點 隊列的頭尾兩端都能在O(1)的時間內進行數據查看、添加和刪除 可以用一個雙鏈表實現 ### 常用的場景 實現一個長度動態變化的窗口或者連續區間 ### leet-code練手 239. 滑動窗口最大值 ~~~ package com.mango.leet.code.hard; /** * 239. 滑動窗口最大值 */ import java.util.*; /** * 給你一個整數數組 nums，有一個大小為?k?的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k?個數字。滑動窗口每次只向右移動一位。 * * 返回 滑動窗口中的最大值 。 * * ? * * 示例 1： * * 輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3 * 輸出：[3,3,5,5,6,7] * 解釋： * 滑動窗口的位置 最大值 * --------------- ----- * [1 3 -1] -3 5 3 6 7 3 * 1 [3 -1 -3] 5 3 6 7 3 * 1 3 [-1 -3 5] 3 6 7 5 * 1 3 -1 [-3 5 3] 6 7 5 * 1 3 -1 -3 [5 3 6] 7 6 * 1 3 -1 -3 5 [3 6 7] 7 * 示例 2： * * 輸入：nums = [1], k = 1 * 輸出：[1] * ? * * 提示： * * 1 <= nums.length <= 105 * -104?<= nums[i] <= 104 * 1 <= k <= nums.length * * * 來源：力扣（LeetCode） * 鏈接：https://leetcode-cn.com/problems/sliding-window-maximum * 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 */ public class LC239 { public static void main(String[] args) { int[] nums = new int[]{1,3,-1,-3,5,3,6,7}; //int[] nums = new int[]{1,3,1,2,0,5}; //int[] nums = new int[]{7,2,4}; System.out.println(Arrays.toString(new Solution().maxSlidingWindow(nums,3))); } static class Solution { /** * * 輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3 * * 輸出：[3,3,5,5,6,7] */ public int[] maxSlidingWindow(int[] nums, int k) { // 結果數組 int[] result = new int[nums.length - k + 1]; // 雙端隊列 Deque<Integer> deque = new LinkedList<>(); for(int i=0;i<nums.length;i++){ // 如果隊列尾值下標的值小于當前數組下標的值，則將尾值下標從雙端隊列中移除 while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){ deque.pollLast(); } // 將當前下標加入到尾部（有可能是最大值下標，也有可能是下一個最大值下標） deque.addLast(i); // 如果雙端隊列中記錄的最大值下標，超過了滑動窗口的值范圍，則移除掉 if(deque.peekFirst() <= i-k){ deque.pollFirst(); } // 給result賦值當前雙端隊列中記錄下標的最大值 if(i >= k-1){ result[i-k+1] = nums[deque.peekFirst()]; } } return result; } } } /** * 2022-03-03 * 思路： * 利用雙端隊列存儲最大值的下標，滑動窗口超出則移除過期值 */ ~~~