剑指 Offer 59 - I. 滑动窗口的最大值

之前遇到微众银行的一道题，一个人，只能看见左边的n个人和右边的m个人，如果左右范围内的人都比他能力值大的话，他就要开始努力了。求最左边的努力的人的编号。
当时我想到的思路就是两个数组存储i用户左右的最小的能力值，然后n时间进行比较，优化时间。没做出来，因为核心就是两边的滑动窗口最小值有问题。

如何在每次窗口滑动后，将 “获取窗口内最大值” 的时间复杂度从 O(k)O(k) 降低至 O(1)O(1) 。

滑动窗口的最大最小值的求解方法其实就是这一题的思路：
image.png
思路很简单：使用一个双端队列，维持非严格单调性，队首为大，队尾为小，在每一次进入的时候，从队尾进入，如果当前进入的元素比队首的还大，那么直接将整个队列出队。这样就可以保证每个区间中的最大值得以保持。
关键是，为什么这样没问题？
其实核心问题在于：如果移动窗口中，队首元素是当前窗口中的最大值，出队了，如何保持新的最大值？
解决这个问题就是通过非严格单调实现的，比如图中第二个窗口，假如第5个元素不是5而是-1，那么此时出窗口的是最大值，进窗口的不是新的最大值，非严格单调，使得我们在这种特殊情况的时候，不是清空整个队列，而是只需要队首出队就可以轻松得到窗口内次大值，并作为下一个窗口最大值即可。
而对次大值的维护，如果是-1的情况，那么我们就是，将-3，-1出队，-1入队，即满足了维护次大值。即，新来的值得存起来，防止他是未来的最大值（现在的次大值）的情况。

  1. impl Solution {
  2.     /// 剑指 Offer 59 - I. 滑动窗口的最大值
  3.     pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
  4.         if nums.len() == 0 || k ==0 { return vec![0] }
  5.         let k = k as usize;
  6.         let mut queue = VecDeque::with_capacity(k);
  7.         let mut res = vec![];
  8.         // 在窗口尚未形成的时候，维护非严格单调减
  9.         for i in 0..k {
  10.             while !queue.is_empty() && *queue.back().unwrap() < nums[i] {
  11.                 queue.pop_back().unwrap();
  12.             }
  13.             queue.push_back(nums[i]);
  14.             println!("{:?}", queue);
  15.         }
  16.         res.push(*queue.front().unwrap());
  17.         // 窗口形成之后,双指针维护窗口
  18.         (1..=(nums.len() - k + 1)).zip(k..nums.len()).for_each(|(i, j)| {
  19.             // 如果出队为当前最大值的时候,直接出
  20.             if *queue.front().unwrap() == nums[i-1] {
  21.                 queue.pop_front().unwrap();
  22.             }
  23.             let now = nums[j];
  24.             // 维护非严格单调递减
  25.             while !queue.is_empty() && *queue.back().unwrap() < now {
  26.                 queue.pop_back().unwrap();
  27.             }
  28.             queue.push_back(now);
  29.             res.push(*queue.front().unwrap());
  30.             println!("{:?}", queue);
  31.         });
  32.         res
  33.     }
  34. }

当然，还有一个更nb的：

    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        // 防止窗口为0的情况
        nums[..].windows(k.max(1) as usize).map(|x|*(x.into_iter().max().unwrap())).collect()
    }