2020/3/15

题目描述

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

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

示例

示例：
输入: 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

提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

进阶：
你能在线性时间复杂度内解决此题吗？

相关标签

堆
Sliding Window

解题思路

• 算法：

1. 双端队列法
   处理前 k 个元素，初始化双向队列。
   遍历整个数组。在每一步 :
   清理双向队列 :

• 只保留当前滑动窗口中有的元素的索引。
• 移除比当前元素小的所有元素，它们不可能是最大的。
  将当前元素添加到双向队列中。
  将 deque[0] 添加到输出中。
  返回输出数组。

1. 动态规划法
   https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetcode-3/

• 复杂度分析：

1. 双端队列法
   时间复杂度：O(N)
   空间复杂度：O(N)

2. 动态规划法
   时间复杂度：O(N)
   空间复杂度：O(N)

源代码

双端队列法

use std::collections::VecDeque;

// 偷懒直接用了之前题目中用过的辅助队列，其实只用一个双端队列+存储下标的方式搞定
struct PriorityQueue {
    // 单向队列
    queue: VecDeque<i32>,
    // 辅助队列
    deque: VecDeque<i32>,
}

impl PriorityQueue {
    fn new() -> PriorityQueue {
        PriorityQueue {
            queue: VecDeque::new(),
            deque: VecDeque::new(),            
        }
    }

    fn push_back(&mut self, val: i32) {
        while let Some(prev_val) = self.deque.back() {
            if *prev_val < val {
                self.deque.pop_back();
            }
            else {
                break;
            }
        }
        self.deque.push_back(val);
        self.queue.push_back(val);
    }

    fn pop_front(&mut self) -> Option<i32> {
        let front = self.queue.pop_front();
        if let Some(front_val) = front {
            if front_val == *self.deque.front().unwrap() {
                self.deque.pop_front();
            }
        }
        front
    }

    fn max_val(&self) -> Option<i32> { 
        if let Some(&val) = self.deque.front() {
            Some(val)
        }
        else {
            None
        }
    }
}

impl Solution {
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let len: usize = nums.len();
        let mut res = vec![];
        if len == 0 {
            return res;
        }
        let mut pq = PriorityQueue::new();

        for i in 0..k as usize {
            pq.push_back(nums[i]);
        }
        res.push(pq.max_val().unwrap());

        for i in k as usize..len {
            pq.push_back(nums[i]);
            pq.pop_front();
            res.push(pq.max_val().unwrap());
        }

        res
    }
}

执行用时 : 4 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗 : 2.6 MB, 在所有 Rust 提交中击败了100.00%的用户

总结

本题中的动态规划解法思路很有趣，值得学习。