36-Sliding-Window-Maximum.md

Sliding Window Maximum

Problem Link

https://leetcode.com/problems/sliding-window-maximum/

---

Pattern

• Deque
• Sliding Window

---

Approach

Maintain a decreasing deque of indices so the front always contains the maximum of the current window.

---

Time Complexity

O(n)

Space Complexity

O(k)

---

Java Solution

import java.util.*;
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] ans = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.pollFirst();
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) deque.pollLast();
            deque.offerLast(i);
            if (i >= k - 1) ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}