求 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中文網其他相關文章！