239.滑动窗口最大值

链接：239.滑动窗口最大值
难度：Hard
标签：队列、数组、滑动窗口、单调队列、堆（优先队列）
简介：给你一个整数数组 nums，有一个大小为  k  的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k  个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

题解 1 - typescript

• 编辑时间：2021-01-02
• 执行用时：4056ms
• 内存消耗：73.1MB
• 编程语言：typescript
• 解法介绍：每次储存最大值进行比较。

function maxSlidingWindow(nums: number[], k: number): number[] {
  if (k === 1) return nums;
  const len = nums.length;
  if (len === k) return [Math.max(...nums)];
  const ans: number[] = [];
  let max = -Infinity;
  let index = 0;
  for (let i = 0; i < k; i++) {
    const num = nums[i];
    if (max < num) {
      max = num;
      index = i;
    }
  }
  ans.push(max);
  for (let i = k; i < len; i++) {
    if (index <= i - k) {
      max = -Infinity;
      for (let j = i - k + 1; j <= i; j++) {
        const num = nums[j];
        if (max < num) {
          max = num;
          index = j;
        }
      }
    } else {
      const num = nums[i];
      if (max < num) {
        max = num;
        index = i;
      }
    }
    ans.push(max);
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-01-02
• 执行用时：324ms
• 内存消耗：72.2MB
• 编程语言：typescript
• 解法介绍：优化题解 1。

function maxSlidingWindow(nums: number[], k: number): number[] {
  const n = nums.length;
  const q: number[] = [];
  for (let i = 0; i < k; i++) {
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }
    q.push(i);
  }
  const ans = [nums[q[0]]];
  for (let i = k; i < n; i++) {
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }
    q.push(i);
    while (q[0] <= i - k) {
      q.shift();
    }
    ans.push(nums[q[0]]);
  }
  return ans;
}

题解 3 - typescript

• 编辑时间：2021-05-08
• 执行用时：5224ms
• 内存消耗：69.8MB
• 编程语言：typescript
• 解法介绍：二分维护数组。

function maxSlidingWindow(nums: number[], k: number): number[] {
  const win = nums.slice(0, k).sort((a, b) => a - b);
  const findIndex = (num: number, l = 0, r = k - 1) => {
    if (l > r) return l;
    const mid = (l + r) >> 1;
    const midNum = win[mid];
    if (midNum < num) return findIndex(num, mid + 1, r);
    else if (midNum > num) return findIndex(num, l, mid - 1);
    else return mid;
  };
  const add = (num: number) => win.splice(findIndex(num), 0, num);
  const del = (num: number) => win.splice(findIndex(num), 1);
  const ans = [win[k - 1]];
  for (let i = k, l = nums.length; i < l; i++) {
    add(nums[i]);
    del(nums[i - k]);
    ans.push(win[k - 1]);
  }
  return ans;
}

题解 4 - typescript

• 编辑时间：2021-05-08
• 执行用时：944ms
• 内存消耗：73.8MB
• 编程语言：typescript
• 解法介绍：利用列表维护最大值。

function maxSlidingWindow(nums: number[], k: number): number[] {
  const list: number[] = [];
  if (k === 0) return list;
  const ans: number[] = [];
  const len = nums.length;
  let index = 0;
  while (index < len) {
    while (list.length !== 0 && list[0] + k <= index) list.shift();
    const num = nums[index];
    while (list.length !== 0 && nums[list[list.length - 1]] < num) list.pop();
    list.push(index++);
    index >= k && ans.push(nums[list[0]]);
  }
  return ans;
}

题解 5 - typescript

• 编辑时间：2021-07-20
• 执行用时：4712ms
• 内存消耗：73.3MB
• 编程语言：typescript
• 解法介绍：单调递减队列。

function maxSlidingWindow(nums: number[], k: number): number[] {
  const n = nums.length;
  const queue: number[] = [];
  const ans: number[] = [];
  for (let i = 0; i < n; i++) {
    const num = nums[i];
    while (queue.length && nums[queue[queue.length - 1]] < num) queue.pop();
    queue.push(i);
    if (i - queue[0] === k) queue.shift();
    if (i + 1 < k) continue;
    ans.push(nums[queue[0]]);
  }
  return ans;
}