製作山脈陣列的最少移除次數-php教程-PHP中文網

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

Barbara Streisand

發布： 2024-11-01 07:33:30

原創

961 人瀏覽過

Minimum Number of Removals to Make Mountain Array

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

難度：難

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

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

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

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

。

範例1：

輸入：
輸出：
說明：

範例2：

輸入：
輸出：
解釋：

約束：

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

提示：

解：

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

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

解決方案概要

辨識增加的子序列長度
:
辨識遞減的子序列長度
:
- 計算rightLIS數組，其中rightLIS[i]表示從i開始（從右到左）的最長遞減子序列的長度。
計算最大山長:
- 對於每個索引 i，其中 0 1 且 rightLIS[i] > 1）。計算 i 處的山長為 leftLIS[i] rightLIS[i] - 1.
得到最小移除量：
- 要刪除的最小元素將是原始陣列長度減去找到的最長山的長度。

讓我們用 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
?>

登入後複製

解釋：

左LIS計算:
- leftLIS[i] 儲存以 i 結尾的遞增子序列的最大長度。我們迭代每個 i，對於每個 i，從 0 迭代到 i-1，找到以 i 結尾的最長子序列。
正確的 LIS 計算:
- rightLIS[i] 儲存從 i 開始的遞減子序列的最大長度。我們從 n-2 向後迭代到 0，對於每個 i，從 n-1 向下迭代到 i 1 以找到從 i 開始的最長子序列。
山脈計算:
- 索引 i 處的有效峰值必須具有 leftLIS[i] > 1 且右LIS[i]> 1. 峰位於 i 的山的長度為 leftLIS[i] rightLIS[i] - 1.
最終計算：
- 所需的最小移除量是原始陣列長度與找到的最大山體長度之間的差值。