pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32>
Expand description
§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
}