Sliding window maximum

Array Queue Sliding Window Heap (Priority Queue) Monotonic Queue

48.5% acceptance

Jan 12, 2026

20285

834

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let mut result = Vec::new();
    let mut deque: std::collections::VecDeque<usize> = std::collections::VecDeque::new();
    
    for i in 0..nums.len() {
      // Remove indices outside the current window
      if let Some(&front) = deque.front() {
        if front + k <= i {
          deque.pop_front();
        }
      }
      
      // Remove indices whose values are less than current value
      while let Some(&back) = deque.back() {
        if nums[back] < nums[i] {
          deque.pop_back();
        } else {
          break;
        }
      }
      
      deque.push_back(i);
      
      // Add to result when window is fully formed
      if i + 1 >= k {
        result.push(nums[*deque.front().unwrap()]);
      }
    }
    
    result
  }
}