力扣热门100题之滑动窗口最大值

张开发
• 2026/4/6 2:53:45 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

力扣热门100题之滑动窗口最大值
核心思路用双端队列 Deque存数组下标保证队列头永远是当前窗口最大值队列里的元素从大到小排列单调递减新元素进来时把队列里比它小的元素全部删掉不可能成为最大值把新元素加入队列检查队头是否超出窗口左边界超出就移除窗口形成后队头就是当前窗口最大值如果在队列中有比当前遍历到的数字小的就会取出来然后再重新添加// 2. 移除队列中比当前元素小的数队尾 while(!deque.isEmpty() nums[i] deque.peekLast()){ deque.pollLast(); }三步核心逻辑移除过期元素窗口左边出去的元素窗口左边界是i - k 1队头下标 左边界 → 已经不在窗口里 →删掉while (!deque.isEmpty() deque.peekFirst() i - k 1)维护单调递减队列当前数≥队列最后一个数说明队列里的数永远不可能成为最大值→全部删掉保证队列从大到小while (!deque.isEmpty() nums[i] nums[deque.peekLast()])收集结果当遍历到第k-1个元素时第一个窗口形成之后每一步队头都是当前窗口最大值直接加入结果if (i k - 1) { res[index] nums[deque.peekFirst()]; }完整代码实现class Solution { public int[] maxSlidingWindow(int[] nums, int k) { // 边界判断 if (nums null || nums.length 0 || k 0) { return new int[0]; } DequeInteger deque new LinkedList(); // 存下标维护单调递减 int n nums.length; int[] res new int[n - k 1]; // 结果数组长度 int index 0; // 结果数组下标 for(int i 0;in;i){ // 1. 移除超出窗口左边界的元素队头 while(!deque.isEmpty() deque.peekFirst() i - k 1){ deque.pollFirst(); } // 2. 移除队列中比当前元素小的数队尾确保单调递减 while(!deque.isEmpty() nums[i] deque.peekLast()){ deque.pollLast(); } //将当前数字下标加入队列 deque.offerLast(i); // 如果当前位置已经形成了窗口 if(i k-1){//当遍历到第 k-1 个元素时第一个窗口形成 // 把队列头部的【当前窗口最大值】放进结果数组 res[index] nums[deque.peekFirst()]; } } return res; } }

更多文章