求 K 尺寸子阵列的功效 I-php教程-PHP中文网

求 K 尺寸子阵列的功效 I

Mary-Kate Olsen

发布： 2024-11-25 00:58:27

原创

644 人浏览过

Find the Power of K-Size Subarrays 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]

约束：

提示：

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

解决方案：

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

问题分解：

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

计划：

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

步骤：

检查子数组是否已排序：
- 具有连续元素的排序子数组应具有以下属性：对于子数组中的每个 i，nums[i 1] - nums[i] == 1。
滑动窗口：
- 对于每个长度为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。