leetcode239

    解法1: 双指针+遍历法

    1. const maxSlidingWindow = function(nums, k) {
    2.     let len = nums.length;
    3.     let left = 0;
    4.     let right = k-1;
    5.       let result = []
    6.     while(right<=len-1){
    7.         result.push(calMax(nums,left,right))
    8.         left++;
    9.         right++;
    10.     }
    11.     return result
    12. };
    14. function calMax(arr,l,r){
    15.     let max = arr[l];
    16.     for(let i = l;i<=r;i++){
    17.         max = Math.max(max,arr[i])
    18.     }
    19.     return max;
    20. }

    时间复杂度O(kn)
    空间复杂度O(n)

    对于解法1，当滑动窗口往后前进一步的时候，比如我从初始位置前进到第二个位置：
    171916004417d924.webp
    此时滑动窗口内的元素少了一个 1，增加了一个 -3——减少的数不是当前最大值，增加的数也没有超越当前最大值，因此最大值仍然是 3。此时我们不禁要想：如果我们能在窗口发生移动时，只根据发生变化的元素对最大值进行更新，那时间复杂度是不是就降低了？

    双端队列可以完美地帮助我们达到这个目的。

    解法2:双端队列法
    解题思路： 使用一个双端队列存储窗口中值的 索引 ，并且保证双端队列中第一个元素索引对应的值永远是最大值（索引对应的值递减的双端队列），那么只需要遍历一次 nums，就可以从双端队列对头取到每次移动时的最大值。

    • 检查队尾元素，依次比较双端队列的队尾与当前元素 i 对应的值，队尾元素值较小时出列，直至不小于当前元素 i 的值时，或者队列为空，这是为了保证当队头出队时，新的队头依旧是最大值。
    • 检查对头元素，看队头元素是否已经被排除在滑动窗口的范围之外了，比较当前元素 i 和双端队列对头元素（索引值），相差 >= k 时对头出列。
    • 当遍历元素的个数 >=k 时，开始将对头元素依次放入结果数组中。
      1. const maxSlidingWindow = function (nums, k) {
      2. let len = nums.length;
      3. let deque = [];
      4. let result = [];
      5. for (let i = 0; i < len; i++) {
      6.   // 将小于当前元素的索引出队
      7.   while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      8.     deque.pop();
      9.   }
      10.   // 当前元素的索引入队
      11.   deque.push(i);
      12.   // 在窗口之外的元素出队
      13.   if (deque[0] < i - k + 1) {
      14.     deque.shift();
      15.   }
      16.   // 遍历的元素个数 >= k时，开始更新结果呢数组
      17.   if (i + 1 >= k) {
      18.     result.push(nums[deque[0]]);
      19.   }
      20. }
      21. return result;
      22. };
      时间复杂度O(n)
      空间复杂度O(n)