千问 LeetCode 239. Sliding Window Maximum Java Implement-北京尧图网络

This is a classic monotonic deque problem. The key idea is to maintain a deque that stores indices of elements in decreasing order of their values — so the front of the deque always points to the current window’s maximum.Core IdeaFor each new element nums[i]:Remove expired indices from the front if they’re outside the window (deque.peekFirst() i - k).Remove smaller elements from the back — if nums[i] is larger, those smaller elements can never be the max again.Add current index to the back.Record the max (front of deque) once the first full window is formed (i k - 1).Java Implementationimport java.util.Deque;import java.util.ArrayDeque;class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums null || nums.length 0 || k 0) {return new int[0];}int n nums.length; int[] result new int[n - k 1]; DequeInteger deque new ArrayDeque(); // stores indices for (int i 0; i n; i) { // 1. Remove indices outside the window if (!deque.isEmpty() deque.peekFirst() i - k) { deque.pollFirst(); } // 2. Remove elements smaller than nums[i] from the back while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 3. Add current index deque.offerLast(i); // 4. Record max once the first window is complete if (i k - 1) { result[i - k 1] nums[deque.peekFirst()]; } } return result; }}Walkthrough with nums [1,3,-1,-3,5,3,6,7], k 3i nums[i] deque (indices) deque (values) result0 1 [0] [1] —1 3 [1] [3] —2 -1 [1,2] [3,-1] 33 -3 [1,2,3] [3,-1,-3] 34 5 [4] [5] 55 3 [4,5] [5,3] 56 6 [6] [6] 67 7 [7] [7] 7Output: [3, 3, 5, 5, 6, 7] ✓ComplexityTime: O(n) — each element is added and removed at most once from the deque.Space: O(k) — the deque holds at most k indices.Key Interview PointsWhy store indices instead of values? Storing indices lets us easily check whether the front element is still within the current window (index i - k).Why when removing from back? Using (not just ) ensures that when equal elements exist, we keep the newer one, which stays in the window longer.Why not a max-heap? A heap gives O(n log k), and you’d also need lazy deletion to handle expired elements. The deque approach is strictly better at O(n).Common bug: Forgetting to remove expired indices before reading the max. Always clean the front first.Want me to also show the sparse table / RMQ approach? It’s O(n log n) preprocessing O(1) per query, useful if the interviewer asks about arbitrary range maximum queries (not just sliding windows).

千问 LeetCode 239. Sliding Window Maximum Java Implement

相关推荐

千问 LeetCode 224. Basic Calculator Java Implement

Outlook / Hotmail 邮箱监控配置流程

AI安全监管，为何越管越松？

更多资讯

STM32寄存器白话手册：手把手寄存器操作点亮LED

6款网络工程师效率神器：从抓包到自动化监控的实战指南

Trae国际版实战：从配置到Builder模式，AI IDE高效开发指南

MyEclipse 10.7汉化完整指南：Babel语言包安装与避坑实践

AI芯片软硬件协同实战：算子融合、DMA调度与硅前验证全解析

impeccable：可验证的工程质量标准与四层落地实践

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？