haar_lib/algo/
sliding_window.rs

1//! スライド最小値
2
3use std::cmp::Reverse;
4use std::collections::VecDeque;
5
6/// 配列のすべての長さkの連続部分列について、その最小値を列挙する。
7///
8/// **Time complexity** $O(|a|)$
9pub fn sliding_minimum<T: Ord + Copy>(a: &[T], k: usize) -> Vec<T> {
10    let n = a.len();
11
12    let mut dq = VecDeque::new();
13    let mut ret = vec![];
14
15    for i in 0..k {
16        while dq.back().is_some_and(|&b| a[b] >= a[i]) {
17            dq.pop_back();
18        }
19        dq.push_back(i);
20    }
21
22    for i in 0..n - k + 1 {
23        while *dq.front().unwrap() < i {
24            dq.pop_front();
25        }
26
27        ret.push(a[*dq.front().unwrap()]);
28
29        while i + k < n && dq.back().is_some_and(|&b| a[b] >= a[i + k]) {
30            dq.pop_back();
31        }
32
33        dq.push_back(i + k);
34    }
35
36    ret
37}
38
39/// 配列のすべての長さkの連続部分列について、その最大値を列挙する。
40///
41/// **Time complexity** $O(|a|)$
42pub fn sliding_maximum<T: Ord + Copy>(a: &[T], k: usize) -> Vec<T> {
43    let s = a.iter().map(Reverse).collect::<Vec<_>>();
44    sliding_minimum(&s, k).into_iter().map(|x| *x.0).collect()
45}
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_minimum() {
53        assert_eq!(sliding_minimum(&[1, 7, 7, 4, 8, 1, 6], 3), [1, 4, 4, 1, 1]);
54    }
55
56    #[test]
57    fn test_maximum() {
58        assert_eq!(sliding_maximum(&[1, 7, 7, 4, 8, 1, 6], 3), [7, 7, 8, 8, 8]);
59    }
60}
haar_lib/algo/sliding_window.rs

haar_lib/algo/
sliding_window.rs
