求 K 尺寸子阵列的功效 I

3254。求 K 尺寸子阵列 I

的威力

难度：中等

主题：数组、滑动窗口

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

数组的幂定义为：

• 如果其所有元素都是连续并且按升序顺序排序，则其最大元素。
• 否则-1。

您需要找到大小为 k 的数字的所有子数组1的^幂。

返回大小为 n - k 1 的整数数组结果，其中 results[i] 是 nums[i..(i k - 1)] 的 幂。

示例1：

• 输入： nums = [1,2,3,4,3,2,5], k = 3
• 输出： [3,4,-1,-1,-1]
• 解释： 有 5 个 nums 大小为 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
• 1 5
• 1

提示：

1. 我们可以使用带有嵌套循环和 HashSet 的强力解决方案吗？

解决方案：

我们可以将任务分解如下：

问题分解：

1. 给定一个长度为 n 的数组 nums 和一个正整数 k。我们需要考虑大小为 k 的所有子数组并计算它们的 幂.
2. 子数组的幂为：
   • 如果所有元素都是连续并且按升序顺序排序，则子数组的最大元素。
   • 否则-1。
3. 我们需要返回一个大小为 n - k 1 的数组，其中每个元素对应于相应子数组的幂。

计划：

1. 滑动窗口方法：我们将在数组上滑动并检查长度为 k 的每个子数组。
2. 检查子数组是否已排序：我们需要检查子数组是否有连续且按升序排序的元素。
3. 返回最大值或-1：如果子数组有效，我们返回最大元素。否则，返回-1。

步骤：

1. 检查子数组是否已排序：
   • 具有连续元素的排序子数组应具有以下属性：对于子数组中的每个 i，nums[i 1] - nums[i] == 1。
2. 滑动窗口：
   • 对于每个长度为k的子数组，检查它是否已排序，如果有效则返回最大元素，否则返回-1。

让我们用 PHP 实现这个解决方案：3254。求 K 尺寸子阵列 I
的功效

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function resultsArray($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(resultsArray([1, 2, 3, 4, 3, 2, 5], 3));  // Output: [3, 4, -1, -1, -1]
print_r(resultsArray([2, 2, 2, 2, 2], 4));  // Output: [-1, -1]
print_r(resultsArray([3, 2, 3, 2, 3, 2], 2));  // Output: [-1, 3, -1, 3, -1]
?>

解释：

• 滑动窗口：我们使用从 i = 0 到 i = n - k 的 for 循环来考虑大小为 k 的所有子数组。对于每个子数组，我们使用 array_slice() 来提取子数组。
• 排序检查：对于每个子数组，我们通过迭代子数组并检查每对连续元素是否相差 1 来检查它是否按连续元素排序。
• 结果：如果子数组有效，我们将子数组的最大值附加到结果中。否则，我们追加 -1。

时间复杂度：

• 我们正在迭代 n - k 1 个子数组。
• 对于每个子数组，我们检查元素是否连续，这需要 O(k) 时间。
• 因此，整体时间复杂度为 O((n - k 1) * k)，简化为 O(n * k)。

边缘情况注意事项：

• 如果 k = 1，则每个子数组都是平凡排序的（它只包含一个元素），并且每个子数组的幂将是该元素本身。
• 如果子数组不连续，则立即返回-1。

示例输出：

1. 对于 nums = [1, 2, 3, 4, 3, 2, 5], k = 3，输出为 [3, 4, -1, -1, -1]。
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]。

该解决方案应该能够有效地解决问题约束。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

---

1. 子数组：子数组是数组中连续的非空元素序列。 ↩

以上是求 K 尺寸子阵列的功效 I的详细内容。更多信息请关注PHP中文网其他相关文章！