Leetcode 2023-07-05 题目分享

1671. 得到山形数组的最少删除次数 [Hard] 题解

得到山形数组的最少删除次数

我们定义 arr 是 山形数组 当且仅当它满足：

• arr.length >= 3
• 存在某个下标 i (1<=i<=arr.length-2)
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • 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 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。

提示：

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 10^9
• 题目保证 nums 删除一些元素后一定能得到山形数组。

思路

1. 山脉题经典思路=>前后缀分解
2. 题解里很多是反向来思考的=>删除的最少，意味着剩下的前后缀递增长度最长。
3. 这就变成了常见问题：最长上升子序列。由于数据规模只有1000，可以直接线性DP求解。
4. 但这里我提供一种正向思考的方法：dp[i]表示前[0，i]个数，选中了第i个数后最少删除次数，使得这些数严格递增。
5. 有一个坑就是，题目的山顶不能在数组开始或结束。就是说[1，2，3]和[3，2，1]是不符合题意的。在最后枚举山顶时，要判断山顶两边是不是没有其他数字了。

代码

var minimumMountainRemovals = function(nums) {
    let handle = arr => {
        let n = arr.length;
        // 最坏情况 第i个数将它左边所有数都删除，只剩一个数。即 dp[i] = i。
        // JS有没有更优雅的方法实现 dp[i] = i ???
        let dp = new Array(n).fill(0).map((v, i)=>i);
        for (let i = 1;i < n;i++){
            for (let j = 0;j < i;j++){
                if (arr[i] <= arr[j]) continue; 
                // 枚举之前遍历过的数，如果比当前小，就可以更新。
                // 即[0，j]删除次数 加上 i-j-1（两个数之间所有其他数都删除）
                dp[i] = Math.min(dp[i], dp[j]+i-j-1);
            }
        }
        return dp;
    };
    let left = handle(nums), right = handle(nums.reverse()).reverse();
    let n = nums.length, ans = n-3;
    for (let i = 0;i < n;i++){
        // 判断山顶两边是不是没有其它数字了
        if (left[i]==i || right[i]==n-1-i) continue;
        ans = Math.min(ans, left[i]+right[i]);
    }
    return ans;
};

复杂度分析

• 时间：O(n²)。
• 空间：O(n)。