# How to Solve the Sliding Window Maximum Problem Efficiently Using a Monotonic Queue

> Master the sliding window maximum problem with a monotonic queue. Achieve O(N) time complexity and find maximums efficiently by processing each element just twice.

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: how-to-guide
- Published: 2026-02-25

---

**Use a monotonic double-ended queue to maintain candidate maximums in decreasing order, achieving O(N) time complexity by processing each element exactly twice.**

The sliding window maximum problem requires finding the maximum value in every contiguous subarray of size `k` within an input array `nums`. While a naive approach recomputes the maximum for each window in `O(k)` time, the [labuladong/fucking-algorithm](https://github.com/labuladong/fucking-algorithm) repository demonstrates how a **monotonic queue** reduces this to linear `O(N)` time and `O(k)` space.

## Understanding the Sliding Window Maximum Problem

Given an array `nums` and an integer `k`, the task is to return an array containing the maximum of each sliding window of size `k` as it moves from left to right across the input.

A brute-force solution iterates through each of the `N - k + 1` windows and scans all `k` elements to find the maximum. This results in `O(N·k)` time complexity, which becomes prohibitively slow for large inputs—such as streaming data or high-frequency trading applications where `N` can reach millions.

## The Monotonic Queue Data Structure

The optimal solution uses a **monotonic queue**—specifically, a double-ended queue (deque) that stores elements in non-increasing order (largest to smallest). This invariant ensures the head of the queue always contains the current window's maximum.

### Core Operations

The monotonic queue supports three essential operations:

1. **`push(n)`**: Add a new element `n` to the queue. Before appending, remove all elements from the **tail** that are smaller than `n`, as they can never become the maximum while `n` remains in the window.
2. **`max()`**: Return the element at the **head** of the queue, which is the current window maximum.
3. **`pop(n)`**: Remove the head element **only if** it equals `n`. This handles the case where the outgoing element is the current maximum; otherwise, the element was already removed by a previous `push` operation.

### Algorithm Walkthrough

As the window slides across `nums`:

- When a new element enters from the right, execute `push(nums[i])`.
- If the window is full (index `i >= k - 1`), record `max()` as the result for this window.
- When the window slides forward, execute `pop(nums[i - k + 1])` to remove the leftmost element if it is still in the queue.

Each element is pushed and popped at most once, yielding amortized `O(1)` time per operation.

## Implementation Details from labuladong/fucking-algorithm

The [labuladong/fucking-algorithm](https://github.com/labuladong/fucking-algorithm) repository provides detailed explanations in Chinese within the file **`数据结构系列/单调队列.md`**, which implements the monotonic queue pattern in Java. The companion file **`算法思维系列/滑动窗口技巧进阶.md`** explains how this structure integrates with the general sliding window framework.

### Java Implementation

The following Java code is adapted from the repository's implementation in `数据结构系列/单调队列.md`:

```java
// Monotonic queue that maintains decreasing order
class MonotonicQueue {
    private final LinkedList<Integer> maxq = new LinkedList<>();

    // Insert element, discarding smaller tail elements
    public void push(int n) {
        while (!maxq.isEmpty() && maxq.getLast() < n) {
            maxq.pollLast();
        }
        maxq.addLast(n);
    }

    // Current maximum (head of the deque)
    public int max() {
        return maxq.getFirst();
    }

    // Remove element from head only if it equals n
    public void pop(int n) {
        if (!maxq.isEmpty() && n == maxq.getFirst()) {
            maxq.pollFirst();
        }
    }
}

// Solution leveraging the monotonic queue
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue window = new MonotonicQueue();
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {                     // Fill the first k-1 elements
                window.push(nums[i]);
            } else {
                window.push(nums[i]);              // Add new element
                res.add(window.max());             // Record current max
                window.pop(nums[i - k + 1]);       // Remove element leaving the window
            }
        }

        // Convert List<Integer> to int[]
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) ans[i] = res.get(i);
        return ans;
    }
}

```

Key implementation details from the repository:
- The `push` method runs in amortized `O(1)` time because each element is inserted and removed at most once from the tail.
- The `pop` method checks only the head, preserving the FIFO order of the original window while maintaining the monotonic property.

### Python Implementation

For comparison, here is a compact Python implementation using `collections.deque` that follows the same logic described in `算法思维系列/滑动窗口技巧进阶.md`:

```python
from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()           # stores indices, decreasing by their values

        res = []

        for i, v in enumerate(nums):
            # Remove indices out of the current window

            if dq and dq[0] < i - k + 1:
                dq.popleft()

            # Maintain decreasing order in the deque

            while dq and nums[dq[-1]] < v:
                dq.pop()

            dq.append(i)

            # Start recording answers when the first window is full

            if i >= k - 1:
                res.append(nums[dq[0]])

        return res

```

This Python version stores **indices** rather than values, which simplifies the out-of-window check (`dq[0] < i - k + 1`) while maintaining the same amortized `O(N)` complexity.

## Complexity Analysis

| Approach | Time Complexity | Space Complexity | Notes |
|----------|----------------|------------------|-------|
| **Naïve** | `O(N·k)` | `O(1)` | Recomputes max for each window independently |
| **Monotonic Queue** | `O(N)` | `O(k)` | Each element pushed and popped at most once |

The **monotonic queue** achieves linear time because each element enters and exits the deque exactly once. The `push` operation may discard multiple elements from the tail, but since each discarded element is removed permanently, the total number of operations across the entire array remains bounded by `O(N)`.

## Summary

- The **sliding window maximum** problem requires finding the maximum in every contiguous subarray of size `k`.
- A **monotonic queue** (deque maintaining non-increasing order) provides the optimal `O(N)` solution.
- The algorithm processes each element exactly twice: once when entering the window (`push`) and once when exiting (`pop`).
- The [labuladong/fucking-algorithm](https://github.com/labuladong/fucking-algorithm) repository provides reference implementations in `数据结构系列/单调队列.md` and `算法思维系列/滑动窗口技巧进阶.md`.

## Frequently Asked Questions

### What is the time complexity of the sliding window maximum algorithm?

The optimal algorithm using a monotonic queue runs in **O(N)** time, where `N` is the length of the input array. Each element is pushed into the deque once and popped at most once, resulting in amortized constant time per element. This is a significant improvement over the naive **O(N·k)** approach that recomputes the maximum for each window independently.

### Why does the monotonic queue use a double-ended queue?

A **double-ended queue (deque)** is essential because the algorithm requires efficient access to both ends. Elements are removed from the **tail** when maintaining the monotonic decreasing order (during `push`), and from the **head** when they slide out of the window (during `pop`). Standard queues only allow head removal, and stacks only allow tail access; the deque provides the O(1) operations required at both ends.

### Can this approach be adapted for minimum instead of maximum?

Yes, the monotonic queue easily adapts to find **sliding window minimums** by reversing the comparison logic. Instead of maintaining the deque in non-increasing order (largest to smallest), maintain it in non-decreasing order (smallest to largest). When pushing a new element, pop from the tail while `nums[dq[-1]] > v` (instead of `<`). The head will then always contain the current window minimum.

### Where can I find the original implementation in the labuladong repository?

The complete Java implementation and theoretical explanation reside in **`数据结构系列/单调队列.md`**, which details the monotonic queue data structure design and amortized analysis. The integration of this structure with the general sliding window algorithmic framework is documented in **`算法思维系列/滑动窗口技巧进阶.md`**. Both files are part of the [labuladong/fucking-algorithm](https://github.com/labuladong/fucking-algorithm) repository and provide the canonical reference for this pattern.