239. 滑动窗口最大值

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

解题思路

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn max_sliding_window(v: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let n = v.len();
        let mut res = vec![];
        let mut q = std::collections::VecDeque::new();
        for i in 0..n {
            if i >= k && v[i - k] == q[0] {
                q.pop_front();
            }
            // add last
            while let Some(&x) = q.back() {
                if x < v[i] { q.pop_back(); }
                else { break }
            }
            q.push_back(v[i]);
            if i >= k - 1 {
                res.push(q[0]);
            }
        }
        res
    }
}
}

学习感想

一开始确实以为大顶堆就行了，其实要用单调栈，之前也有做过单调栈的题目

单调队列是不能够删除一个指定的元素的，单调栈里维护需要的最大值

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        use std::collections::VecDeque;
        let mut v: VecDeque<i32> = VecDeque::new();
        let k: usize = k as usize;
        let mut res: Vec<i32> = vec![];
        for idx in 0 .. nums.len() {
            if idx >= k  {
                let to_delete: i32 = nums[idx - k];
                if to_delete == v[0] { v.pop_front(); }
            }
            let cur: i32 = nums[idx];
            while let Some(&bck) = v.back() {
                if bck < cur {
                    v.pop_back();
                } else { break }
            }
            v.push_back(cur);
            if idx >= k - 1 { res.push(v[0]); }
        }
        res
    }
}
}