LeetCode #3254: 长度为 K 的子数组的能量值 I

2024-11-23 01:11 (GMT+8) 阅读时间 0 分钟 LeetCodeLeetCode-MediumJavaScriptTypeScript

PS. #3254 和 #3255 是同一道题

题干

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

如果所有元素都是依次连续且上升的，那么能量值为最大的元素。
否则为 -1 。

你需要求出 nums 中所有长度为 k 的子数组的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i..(i + k - 1)] 的能量值。

示例

示例 1：

输入：nums = [1,2,3,4,3,2,5], k = 3

输出：[3,4,-1,-1,-1]

解释：

nums 中总共有 5 个长度为 3 的子数组：

[1, 2, 3] 中最大元素为 3 。 [2, 3, 4] 中最大元素为 4 。 [3, 4, 3] 中元素不是连续的。 [4, 3, 2] 中元素不是上升的。 [3, 2, 5] 中元素不是连续的。

示例 2：

输入：nums = [2,2,2,2,2], k = 4

输出：[-1,-1]

示例 3：

输入：nums = [3,2,3,2,3,2], k = 2

输出：[-1,3,-1,3,-1]

提示

1 <= n == nums.length <= 500
1 <= nums[i] <= 10^5
1 <= k <= n

首先是一个没什么用的小优化，这题返回的数组长度是可以算出来的，有 $n - (k - 1)$ 个元素；主循环也可以在 $n - k$ 位置处结束。

超时解法：滑动窗口

其实我这种半路出家的算法也不精，所以可能找的原型算法出处不一定是对的。不过这题我自己觉得和 KMP 利用已有信息的思路比较像，就当做是解决特定问题的 KMP 变种吧。

KMP 算法的核心是利用已知信息，避免重复计算。那么在遍历这道题过程中的已知信息会是什么呢？就是当前窗口是否连续上升，以及当前窗口内的最大值，以及当前的指针位置。

假设当前的数组为 [3,2,3,4,5,4]，窗口大小为 3，指针从 0 开始，那么：

如果当前窗口内元素不是连续上升元素，那么当前窗口的能量值就是 -1，指针往后移动一个元素。（感觉这里也能优化，比如记录到第几位为止是连续上升，但是没精力想了）
如果当前窗口内的元素是连续上升元素，并且窗口后第一个元素和窗口内最后一个元素也构成连续上升数列，那么已知当前窗口的能量值（数组中的最大值）之后，后一个窗口的能量值就是当前窗口的能量值 + 1，指针往后移动一个元素。
如果当前窗口内元素是连续上升元素，但是窗口后第一个元素和窗口内最后一个元素不构成连续上升数列，记录当前窗口的能量值之后，指针就可以直接跳到 i + k 位置。

此处指针的位置就是 results 数组的下标。

OK，开写。

TypeScript

function resultsArray(nums: number[], k: number): number[] {
  const n = nums.length;
  if (k === 1) return nums;

  const results = Array(n - k + 1).fill(-1);
  let pos = 0;

  while (pos < n - k + 1) {
    if (isAscending(nums, pos, k)) {
      results[pos] = nums[pos] + k - 1; // 连续递增,最大值就是首项 + k-1

      // 检查下一个窗口的第一个元素是否构成连续上升
      if (nums[pos + k] === nums[pos] + k) {
        results[pos + 1] = nums[pos + k];
        pos += 2;
      } else {
        pos += k;
      }
    } else {
      pos++;
    }
  }

  return results;
}

function isAscending(nums: number[], start: number, k: number): boolean {
  for (let i = 1; i < k; i++) {
    if (nums[start + i] !== nums[start + i - 1] + 1) {
      return false;
    }
  }
  return true;
}

我去，怎么超时了。看看还有没有可以优化的地方。

优化解法：计算 combo

注意到超时的样例是一个超长的数组，有五万多个元素，并且 k 也达到了五万多个。这样就算在第一步把循环数砍成了 $n - k + 1$ ，题解也需要循环 $k^{n}$ 次。上面的答案已经是经过几轮优化的结果了，砍掉了不必要的判断，甚至连变量个数都尽可能砍了，按我目前的水平应该很难继续优化了。

确实该超，认了

再重新思考一下符合条件的窗口会有什么特征。首先在第 k 个元素之前是不会出现符合要求的窗口的，因为窗口至少需要有 k 个元素。这就有点像打音游时的 combo，首先需要一定 combo 数才会显示，如果 combo 中间断了的话就会重置回 1.

这样的话，可以先遍历前 k 个元素，看看第一个窗口是不是符合要求。然后依次往后递推，如果某一个地方 combo 断了，就重置回 1. 理论上这样可以把时间复杂度砍到 $O (n)$ ，这总不能不过吧？

那么 result 数组的第一个值就是第一个窗口的能量值，第一个窗口出现时，指针应该至少经过了 k 个元素。设指针位置为 i，转换能得到此时的 result 位置为 $(i + 1) - k$ （因为数组下标从 0 开始，但是 k 是从 1 开始的，因此要补足一位）。

TypeScript

function resultsArray(nums: number[], k: number): number[] {
  const n = nums.length;
  if (k === 1) return nums; // 如果 k 是 1，那么每个元素都是能量值，提前返回秒了
  const results = Array(n - k + 1).fill(-1);
  let combo = 1;
  for (let pos = 0; pos < n; pos++) {
    if (nums[pos] === nums[pos - 1] + 1) {
      combo++;
    } else {
      combo = 1;
    }
    if (combo >= k) {
      results[pos + 1 - k] = nums[pos];
    }
  }
  return results;
}

效果拔群，但是看了一眼比我快的超人，0ms 的解法跟第二版一样，还能接受是误差，但是 2ms 的代码示例用的跟我上面超时的那版复杂度应该是一样的吧……

LeetCode #3254: 长度为 K 的子数组的能量值 I ​

超时解法：滑动窗口 ​

优化解法：计算 combo ​

LeetCode #3254: 长度为 K 的子数组的能量值 I

超时解法：滑动窗口

优化解法：计算 combo