求 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。