力扣|力扣 - 剑指 Offer 59 - I. 滑动窗口的最大值力扣-剑指Offer59-I.滑动窗口的最

题目 【力扣|力扣 - 剑指 Offer 59 - I. 滑动窗口的最大值】剑指 Offer 59 - I. 滑动窗口的最大值
思路1（单调队列）

使用单调（递减）队列，保持队列中的元素是递减顺序，队列头保存的是当前窗口中最大的元素
首先先模拟建立第一个窗口，同时获取第一个窗口的最大值（就是队头元素）
然后每次窗口移动的时候都要判断移出去的元素是否是最大的元素：将窗口最左边的元素和队列头元素进行比较，如果相等，则需要将队头的元素移除，说明窗口的最大值被移出去了，需要寻找新的最大值。而队列头的第二个元素是第二大元素，不过还要和即将进入新窗口的那个元素进行比较

代码

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int length = nums.length; if (length == 0 || k == 0) { return new int[0]; }// Java内置的双端队列 Deque queue = new LinkedList<>(); int[] res = new int[length - k + 1]; // 先初始化第一个窗口 for (int i = 0; i < k; i++) { while (!queue.isEmpty() && queue.peekLast() < nums[i]) { queue.removeLast(); } queue.addLast(nums[i]); } // 获取第一个窗口的最大值 res[0] = queue.peekFirst(); // 移动接下来的窗口 for (int i = k; i < length; i++) { // 要判断窗口右移时，出队的元素是否是当前最大元素 if (queue.peekFirst() == nums[i-k]) { queue.removeFirst(); } // 保持单调队列递减，此时队首的元素就是当前窗口的最大与阿苏 while (!queue.isEmpty() && queue.peekLast() < nums[i]) { queue.removeLast(); } queue.addLast(nums[i]); res[i-k+1] = queue.peekFirst(); }return res; } }

复杂度分析