likes
comments
collection
share

Rust算法题：用双端队列解决滑动窗口最大值

作者站长头像
站长
· 阅读数 25

题目：

滑动窗口最大值是一个经典的算法问题，通常在数据流处理和时间序列分析中遇到。这个问题的目标是从一个整数数组中，找到每个大小为 k 的滑动窗口的最大值。给定一个数组 nums 和窗口大小 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

再看文章讲解之前，自己可以尝试写一下：力扣题目链接

题目分析

这个问题可以用几种方法解决，但一个非常高效的方法是使用双端队列（deque）。双端队列可以从两端高效地添加和移除元素，这使得它非常适合解决滑动窗口问题。下面是具体的算法步骤：

双端队列的主要操作包括：

  • push_front: 在队列的前端添加一个元素。
  • pop_front: 移除并返回队列前端的元素。
  • push_back: 在队列的后端添加一个元素。
  • pop_back: 移除并返回队列后端的元素。
  • front: 访问队列前端的元素。
  • back: 访问队列后端的元素。

Rust中的双端队列

在 Rust 语言中，双端队列的实现是通过标准库中的 std::collections::VecDeque 提供的。VecDeque 是基于一个可增长的环形缓冲区，这使得它在两端添加或删除元素时都具有较高的效率。VecDeque 支持上述所有双端队列操作，并且其性能通常很适合在需要快速从两端修改数据的场合。

算法实现

  1. 初始化：使用一个双端队列来存储数组 nums 中的元素的索引，而不是元素值本身。这样可以更方便地知道何时一个元素已经不在窗口内了。

  2. 维护队列：遍历数组 nums，对于每个元素做以下操作：

    • 如果队列不为空，且队列头部的索引已经不在窗口内（即索引小于当前元素索引减去窗口大小），则从队列头部移除该索引。
    • 从队列尾部开始，移除所有比当前元素小的元素的索引，因为这些元素不会是窗口的最大值。
    • 将当前元素的索引添加到队列尾部。
    • 如果窗口已经形成（即遍历的元素数量大于等于窗口大小 k），则队列的头部元素就是当前窗口的最大值。

  3. 输出结果：将队列头部的元素（当前窗口的最大值）添加到结果数组中。

现在，让我们用 Rust 来实现这个算法：

pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        use std::collections::VecDeque;
        let mut res = vec![];
        let mut queue = VecDeque::with_capacity(k as usize);
        for (i, &v) in nums.iter().enumerate() {
            // 如果队列长度超过 k，那么需要移除队首过期元素
            if i - queue.front().unwrap_or(&0) == k as usize {
                queue.pop_front();
            }
            while let Some(&index) = queue.back() {
                if nums[index] >= v {
                    break;
                }
                // 如果队列第一个元素比当前元素小，那么就把队列第一个元素弹出
                queue.pop_back();
            }
            // 将当前元素索引加入队尾
            queue.push_back(i); 
            // 当窗口的长度为k时，队首元素即为当前窗口的最大值
            if i >= k as usize - 1 {
                res.push(nums[queue[0]]);
            }
        }
        res 
}

在这段代码中，我们使用了 Rust 的标准库中的 VecDeque 来作为双端队列。通过在遍历数组的每一步中维护队列，我们能够有效地计算每个窗口的最大值，并将结果存储在 result 向量中。 下面我们继续对其进行时间复杂度和空间复杂读的分析 下面我将用表格的形式说明如何一步步使用双端队列处理数组 [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小为3的例子。

滑动窗口最大值演示

StepCurrent WindowDeque State (Indexes)Deque ValuesOutput Value (Max)
1[1][0][1]-
2[1, 3][1][3]-
3[1, 3, -1][1, 2][3, -1]3
4[3, -1, -3][1, 2, 3][3, -1, -3]3
5[-1, -3, 5][4][5]5
6[-3, 5, 3][4, 5][5, 3]5
7[5, 3, 6][ 6][6]6
8[3, 6, 7][7][7]7

分步解释

  • Step 1-2: 队列初始化并添加元素。当遇到元素 3 时，由于 3 大于 1，所以 1 被从队列中移除。
  • Step 3: 完成第一个窗口，此时窗口内元素为 [1, 3, -1]，队列为 [1, 2]，表示窗口中最大值为 3。
  • Step 4: 窗口向右移动一位，加入 -3，移除 1，队列依然保持 [1, 2, 3]，输出仍为最大值 3。
  • Step 5: 窗口移动，加入 5，由于 5 大于窗口内所有其他元素，所有前面的元素索引被从队列中移除，只剩 [4]。
  • Step 6: 继续移动窗口，加入 3。由于 3 小于 5，所以队列变为 [4, 5]。
  • Step 7: 再次移动窗口，加入 6，此时 6 大于 3 但小于 5，队列调整为 [4, 6]，但窗口移动使得 5 不再在窗口内，因此队列变为 [6]。
  • Step 8: 最后一个窗口为 [3, 6, 7]，加入 7 后，所有其他索引都被从队列中移除，因为 7 是新的最大值。

时间复杂度

时间复杂度是 O(n) ，其中 n 是数组的长度。这是因为每个元素只会被加入和移除队列各一次。尽管在每个窗口位置，队列可能会多次进行添加和移除操作，但每个元素最终只会进入和离开队列一次。因此，所有操作加起来的总时间复杂度是线性的。这种算法的效率在于我们维护了一个单调递减的队列，使得我们可以快速得到每个窗口的最大值。

空间复杂度

空间复杂度是 O(k) ，其中 k 是滑动窗口的大小。这是因为双端队列在最坏情况下会存储接近 k 个元素（即当窗口完全滑过数组时）。我们只在队列中保存当前窗口可能的最大值的候选元素的索引，而这些候选元素的数量最多不会超过窗口的宽度 k。Pomelo_刘金。转载请注明原文链接。感谢！

转载自:https://juejin.cn/post/7362065407137300519
评论
请登录