滑动窗口最大值-困难

难度：困难

题目描述：
给定一个数组 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

1
2
3
4
5
6
7
8
9
10
11
12
13

解题思路： ```javascript var maxSlidingWindow = function(nums, k) { let maxstack = []; function getMax(data){ let max = data[0]; for(let i= 0; i < data[i]){ max= data[i] } } return max } let j = 0 while(j + k <= nums.length){ let max = getMax(nums.slice(0+j, k+j)) maxstack.push(max) j++ } return maxstack; }; ```

双向队列
维持单调递减队列
每次 push 元素时，将队列中更小元素删除，直到不小时
每次 pop 元素时，如果是更小的元素在 push 时就已经删除了，只需要判断是否是头部最大值，是再删除一遍头部元素即可

var maxSlidingWindow = function (nums, k) {
  let n = nums.length;
  class slideWindow {
    constructor() {
      this.data = [];
    }
    push(val) {
      let data = this.data;
      while (data.length > 0 && data[data.length - 1] < val) {
        data.pop();
      }
      data.push(val);
    }
    pop(val) {
      let data = this.data;
      if (data.length > 0 && data[0] === val) {
        data.shift();
      }
    }
    max() {
      return this.data[0];
    }
  }
  let res = [];
  let windows = new slideWindow();
  for (let i = 0; i < n; i++) {
    if (i < k - 1) {
      windows.push(nums[i]);
    } else {
      windows.push(nums[i]);
      res.push(windows.max());
      windows.pop(nums[i - k + 1]);
    }
  }
  return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

动态规划

var maxSlidingWindow = function (nums, k) {
  let n = nums.length;
  if (n == 0) return [];
  if (k == 1) return nums;
  let res = [];
  let left = new Array(n),
    right = new Array(n);
  left[0] = nums[0];
  right[n - 1] = nums[n - 1];
  for (let i = 1; i < n; i++) {
    if (i % k == 0) left[i] = nums[i];
    else left[i] = Math.max(left[i - 1], nums[i]);
    let j = n - i - 1;
    if ((j + 1) % k == 0) right[j] = nums[j];
    else right[j] = Math.max(right[j + 1], nums[j]);
  }
  for (let i = 0; i < n - k + 1; i++) {
    res[i] = Math.max(left[i + k - 1], right[i]);
  }
  return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

← 最小栈-简单数组中的第 K 个最大元素-中等 →

# 滑动窗口最大值-困难

滑动窗口最大值-困难