製作山脈陣列的最少移除次數

1671。製作山陣的最少移除次數

難度：難

主題：陣列、二分查找、動態規劃、貪心

你可能還記得，陣列 arr 是一個 山數組 當且僅當：

• arr.length >= 3
• 存在一些索引 i (0-indexed)，其中 0
  我
arr[0] arr[i]> arr[i 1] > ...>> arr[arr.length - 1]

給定一個整數數組 nums，返回要刪除的最小個元素，以使 nums 成為山數組

。

範例1：

• 輸入：
nums = [1,3,1]
• 輸出：
0
• 說明：
陣列本身就是一個山數組，所以我們不需要刪除任何元素。

範例2：

• 輸入：
nums = [2,1,1,5,6,2,3,1]
• 輸出：
3
• 解釋：
一個解是刪除索引 0、1 和 5 處的元素，使陣列 nums = [1,5,6,3,1]。

約束：

3 1 9
保證你可以用nums製作一個山形陣列。

提示：

考慮相反的方向而不是最小元素來刪除最大山子序列
想想 LIS，它有點接近

解：

我們可以使用動態規劃方法，其思想是找到最大山子序列，而不是直接計算要刪除的元素。此方法是基於為數組中的每個位置找到兩個最長遞增子序列（LIS）：一個為從左到右，另一個為從右到-離開

。一旦我們有了盡可能長的山子序列，原始數組長度和該子序列長度之間的差異將為我們提供要刪除的最少元素。

解決方案概要

1. 辨識增加的子序列長度

   :
   計算 leftLIS 數組，其中 leftLIS[i] 表示以 i 結尾的最長遞增子序列的長度（從左到右）。

2. 辨識遞減的子序列長度

   :
   • 計算rightLIS數組，其中rightLIS[i]表示從i開始（從右到左）的最長遞減子序列的長度。

3. 計算最大山長:

   • 對於每個索引 i，其中 0 1 且 rightLIS[i] > 1）。計算 i 處的山長為 leftLIS[i] rightLIS[i] - 1.

4. 得到最小移除量：

   • 要刪除的最小元素將是原始陣列長度減去找到的最長山的長度。

讓我們用 PHP 實作這個解：1671。製作山脈陣列的移除次數最少

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

// Example usage
$nums1 = [1, 3, 1];
echo minimumMountainRemovals($nums1); // Output: 0

$nums2 = [2, 1, 1, 5, 6, 2, 3, 1];
echo minimumMountainRemovals($nums2); // Output: 3
?>

解釋：

1. 左LIS計算:

   • leftLIS[i] 儲存以 i 結尾的遞增子序列的最大長度。我們迭代每個 i，對於每個 i，從 0 迭代到 i-1，找到以 i 結尾的最長子序列。

2. 正確的 LIS 計算:

   • rightLIS[i] 儲存從 i 開始的遞減子序列的最大長度。我們從 n-2 向後迭代到 0，對於每個 i，從 n-1 向下迭代到 i 1 以找到從 i 開始的最長子序列。

3. 山脈計算:

   • 索引 i 處的有效峰值必須具有 leftLIS[i] > 1 且右LIS[i]> 1. 峰位於 i 的山的長度為 leftLIS[i] rightLIS[i] - 1.

4. 最終計算：

   • 所需的最小移除量是原始陣列長度與找到的最大山體長度之間的差值。

複雜性分析

• 時間複雜度：O(n²)，由於LIS計算中的雙循環。
• 空間複雜度：O(n)，用於儲存leftLIS和rightLIS陣列。

此解決方案確保我們找到最大的山脈子序列並計算實現山脈陣列所需的最小移除量。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是製作山脈陣列的最少移除次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！