leetcode/
max_sliding_window.rs

1//! # 239. 滑动窗口最大值
2//!
3//! 难度 困难
4//!
5//! 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
6//!
7//! 返回滑动窗口中的最大值。
8//!
9//!
10//! ## 示例 1：
11//!
12//! ```text
13//! 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
14//! 输出：[3,3,5,5,6,7]
15//! 解释：
16//! 滑动窗口的位置                最大值
17//! ---------------               -----
18//! [1  3  -1] -3  5  3  6  7       3
19//!  1 [3  -1  -3] 5  3  6  7       3
20//!  1  3 [-1  -3  5] 3  6  7       5
21//!  1  3  -1 [-3  5  3] 6  7       5
22//!  1  3  -1  -3 [5  3  6] 7       6
23//!  1  3  -1  -3  5 [3  6  7]      7
24//! ```
25//!
26//! ## 示例 2：
27//!
28//! ```text
29//! 输入：nums = [1], k = 1
30//! 输出：[1]
31//! ```
32//!
33//! ## 示例 3：
34//!
35//! ```text
36//! 输入：nums = [1,-1], k = 1
37//! 输出：[1,-1]
38//! ```
39//!
40//! ## 示例 4：
41//!
42//! ```text
43//! 输入：nums = [9,11], k = 2
44//! 输出：[11]
45//! ```
46//!
47//! ## 示例 5：
48//!
49//! ```text
50//! 输入：nums = [4,-2], k = 2
51//! 输出：[4]
52//! ```
53//!
54//!
55//! ## 提示：
56//!
57//! * `1 <= nums.length <= 10^5`
58//! * `-104 <= nums[i] <= 10^4`
59//! * `1 <= k <= nums.length`
60//!
61//! See [leetcode](https://leetcode-cn.com/problems/sliding-window-maximum/)
62use std::collections::VecDeque;
63
64pub struct Solution;
65
66impl Solution {
67    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
68        assert!(k >= 1 && k <= nums.len() as i32);
69        let k = k as usize;
70        let mut iter = nums.iter().enumerate();
71        let queue = iter.by_ref().take(k - 1)
72        .fold(VecDeque::new(), |mut queue, (i, &v)| {
73            while let Some(&(_, last)) = queue.back() {
74                if last < v {
75                    queue.pop_back();
76                } else {
77                    break;
78                }
79            }
80            queue.push_back((i, v));
81            queue
82        });
83
84        iter.scan(queue, |queue, (i, &v)| {
85            while let Some(&(i0, _)) = queue.front() {
86                if i0 < i + 1 - k {
87                    queue.pop_front();
88                } else {
89                    break;
90                }
91            }
92            while let Some(&(_, last)) = queue.back() {
93                if last < v {
94                    queue.pop_back();
95                } else {
96                    break;
97                }
98            }
99            queue.push_back((i, v));
100            Some(queue.front().unwrap().1)
101        })
102        .collect()
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109
110    #[test]
111    fn test() {
112        let cases = vec![
113            ((vec![1,3,-1,-3,5,3,6,7], 3), vec![3,3,5,5,6,7]),
114        ];
115
116        for ((nums, k), expect) in cases {
117            assert_eq!(expect, Solution::max_sliding_window(nums, k));
118        }
119    }
120}
leetcode/max_sliding_window.rs

leetcode/
max_sliding_window.rs
