1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

1
2

输入：nums = [1], k = 1
输出：[1]

1
2

输入：nums = [1,-1], k = 1
输出：[1,-1]

1
2

输入：nums = [9,11], k = 2
输出：[11]

1
2

输入：nums = [4,-2], k = 2
输出：[4]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

    /*
     * ## 解题思路
     * 1. 遍历序列；
     * 2. 使用一个deque来模拟大顶heap，用来记录当前窗口中元素的下标i；
     * 3. curHeap[0]为当前窗口最大元素下标；
     * 4. 遍历时，如果curHeap元素个数>=k(i-curHeap[0]), 则收缩左边元素； 
     * 5. 右侧弹出curHeap中所有<nums[i]的元素, 以保证对
     * 6. 将i加入到curHeap；
     * 7. 从k步开始，依次收集curHeap[0], 即为每个滑窗中的最大元素；
     */
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //边界条件
        if(k==0) return {};

        vector<int> res;
        deque<int> curHeap; //当前窗口中,按序排列的值下标

        for(int i=0; i<nums.size(); i++) {
            //窗口中数间隔>=k, 弹出左侧元素，缩小窗口；
            if (!curHeap.empty() && i-curHeap.front() >= k) {
                curHeap.pop_front();
            }
            //弹出窗口右侧所有<nums[i]的元素；
            while(!curHeap.empty() && nums[curHeap.back()] < nums[i]) {
                curHeap.pop_back();
            }
            //将当前坐标加入窗口
            curHeap.push_back(i);

            //i>k开始，窗口
            if (i>k) {
                res.push_back(nums[curHeap.front()]);
            }
        }

        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

// @lc code=start
use std::collections::BinaryHeap;

impl Solution {
    /// ## 解题思路
    /// - 优先队列/二叉堆
    /// 1. 对于窗口内的元素,维持一个二叉堆(大顶堆), 则堆顶元素即为当前窗口内的最大元素;
    /// 2. 考虑到窗口滑动时,
    ///    会同时有元素进入和离开窗口,在维持堆结构时,需保证堆中元素最大个数不超过窗口大小;
    /// 3. 为此,可使用(val, index)作为堆的键;
    /// 4. 窗口移动时,每增加一个元素到堆中, 同时判断堆顶元素的index是否落入当前窗口范围内;
    /// 5. 如果堆顶元素的index<i-k, 则堆顶元素不在窗口范围内, 则移除该堆顶元素;
    /// 6. 依次输出合法的堆顶元素val即为最终结果;
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut ret_vec = vec![];
        let k = k as usize;
        if k == 0 {
            return ret_vec;
        }
        let mut heap = BinaryHeap::new();
        //遍历各个元素
        nums.iter().enumerate().for_each(|(i, &n)| {
            // 将当前元素和index push到优先队列中
            heap.push((n, i));
            // 依次移除所有不在窗口之内的堆顶元素
            while let Some(&(_, l)) = heap.peek() {
                // 如果堆顶元素index
                if i - l > k - 1 {
                    heap.pop();
                } else {
                    break;
                }
            }
            // 当i>=k-1时, 说明已经生成完整窗口
            if i >= k - 1 {
                //获取堆顶元素, 为当前窗口的最大值
                if let Some(&(top, _)) = heap.peek() {
                    ret_vec.push(top);
                }
            }
        });

        ret_vec
    }
}
// @lc code=end

struct Solution;

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(
            Solution::max_sliding_window(vec![1, 3, -1, -3, 5, 3, 6, 7], 3),
            vec![3, 3, 5, 5, 6, 7]
        );
    }
}