题目：
滑动窗口最大值是一个经典的算法问题，通常在数据流处理和时间序列分析中遇到。这个问题的目标是从一个整数数组中，找到每个大小为 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 支持上述所有双端队列操作，并且其性能通常很适合在需要快速从两端修改数据的场合。
算法实现
-
初始化：使用一个双端队列来存储数组
nums中的元素的索引，而不是元素值本身。这样可以更方便地知道何时一个元素已经不在窗口内了。 -
维护队列：遍历数组
nums，对于每个元素做以下操作：- 如果队列不为空，且队列头部的索引已经不在窗口内（即索引小于当前元素索引减去窗口大小），则从队列头部移除该索引。
- 从队列尾部开始，移除所有比当前元素小的元素的索引，因为这些元素不会是窗口的最大值。
- 将当前元素的索引添加到队列尾部。
- 如果窗口已经形成（即遍历的元素数量大于等于窗口大小
k），则队列的头部元素就是当前窗口的最大值。
-
输出结果：将队列头部的元素（当前窗口的最大值）添加到结果数组中。
现在，让我们用 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
}
fn main() {
let nums = vec![1,3,-1,-3,5,3,6,7];
let k = 3;
let max_values = max_sliding_window(nums, k);
println!("{:?}", max_values); // 输出应为 [3, 3, 5, 5, 6, 7]
}
在这段代码中，我们使用了 Rust 的标准库中的 VecDeque 来作为双端队列。通过在遍历数组的每一步中维护队列，我们能够有效地计算每个窗口的最大值，并将结果存储在 result 向量中。最后，我们在 main 函数中测试了这个函数，以确保其正确性。这样我们就通过双端队列是西安了这个算法，下面我们继续对其进行时间复杂度和空间复杂读的分析
时间复杂度
时间复杂度是 O(n) ，其中 n 是数组的长度。这是因为每个元素只会被加入和移除队列各一次。尽管在每个窗口位置，队列可能会多次进行添加和移除操作，但每个元素最终只会进入和离开队列一次。因此，所有操作加起来的总时间复杂度是线性的。这种算法的效率在于我们维护了一个单调递减的队列，使得我们可以快速得到每个窗口的最大值。
空间复杂度
空间复杂度是 O(k) ，其中 k 是滑动窗口的大小。这是因为双端队列在最坏情况下会存储接近 k 个元素（即当窗口完全滑过数组时）。我们只在队列中保存当前窗口可能的最大值的候选元素的索引，而这些候选元素的数量最多不会超过窗口的宽度 k。Pomelo_刘金。转载请注明原文链接。感谢！