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

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 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 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:

// 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:

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 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 repository and provide the canonical reference for this pattern.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}