Function leetcode_for_rust::cd0239_sliding_window_maximum::max_sliding_window

pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32>

Solutions

Approach 1: Deque

• Time complexity: O(n)

• Space complexity: O(k)

use std::collections::VecDeque;

pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let mut deque = VecDeque::new();
    let mut result = vec![];
    let mut start = 0;
    let k = k as usize;

    for index in 0..nums.len() as usize {
        while !deque.get(start).is_none() && nums[*deque.back().unwrap()] < nums[index] {
            deque.pop_back();
        }

        deque.push_back(index);

        if index >= k && *deque.get(start).unwrap() == (index - k) {
            start += 1;
        }

        if index >= k - 1 {
            result.push(nums[*deque.get(start).unwrap()]);
        }
    }

    result
}

Approach 2: Deque

• Time complexity: O(n)

• Space complexity: O(k)

use std::collections::VecDeque;

pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let mut window = VecDeque::new();
    let mut result = vec![];
    let k = k as usize;

    for i in 0..nums.len() {
        if i > k && window[0] <= i - k {
            window.pop_front();
        }

        while !window.is_empty() && nums[*window.back().unwrap()] <= nums[i] {
            window.pop_back();
        }

        window.push_back(i);

        if i >= k - 1 {
            result.push(nums[*window.front().unwrap()]);
        }
    }
    result
}