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).