Hard

题目描述

你可能还记得，当且仅当满足以下条件时，数组 arr 是一个山形数组：

  • arr.length >= 3
  • 存在某个下标 i（0 < i < arr.length - 1）使得：
    • 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 的元素，使数组变为 nums = [1,5,6,3,1]。

约束条件：

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^9
  • 题目保证可以从 nums 得到一个山形数组。

提示：

  • 思考相反的方向，不是最少删除元素，而是最长的山形子序列
  • 考虑最长递增子序列（LIS），这与此问题很相似

解题思路

解题思路

这道题要求找到最少删除次数使数组变成山形数组。我们可以换个角度思考：找到最长的山形子序列，删除次数就是总长度减去最长山形子序列的长度。

山形数组的特点是存在一个峰值，左边严格递增，右边严格递减。对于每个可能的峰值位置 i，我们需要：

  1. 计算以 i 结尾的最长递增子序列长度（LIS）
  2. 计算以 i 开始的最长递减子序列长度（LDS）

具体步骤：

  1. 计算 LIS：对每个位置 i，计算 nums[0…i] 中以 nums[i] 结尾的最长递增子序列长度
  2. 计算 LDS：对每个位置 i，计算 nums[i…n-1] 中以 nums[i] 开始的最长递减子序列长度
  3. 枚举峰值：对每个可能的峰值位置 i（要求左右两边都至少有一个元素），计算山形长度 = LIS[i] + LDS[i] - 1
  4. 找最优解：最长山形子序列长度为所有可能峰值的最大值，最少删除次数 = n - 最长山形长度

可以使用动态规划（O(n²)）或二分查找优化（O(n log n)）来计算 LIS 和 LDS。这里采用 O(n²) 的 DP 方法，思路更清晰。

山形数组要求峰值两侧都必须有元素，所以 LIS[i] >= 2 且 LDS[i] >= 2 的位置才能作为有效峰值。

代码实现

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        
        // 计算以每个位置结尾的最长递增子序列长度
        vector<int> lis(n, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    lis[i] = max(lis[i], lis[j] + 1);
                }
            }
        }
        
        // 计算以每个位置开始的最长递减子序列长度
        vector<int> lds(n, 1);
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] > nums[j]) {
                    lds[i] = max(lds[i], lds[j] + 1);
                }
            }
        }
        
        // 找最长的山形子序列
        int maxMountain = 0;
        for (int i = 1; i < n - 1; i++) {
            // 必须左右两边都有元素才能构成山形
            if (lis[i] >= 2 && lds[i] >= 2) {
                maxMountain = max(maxMountain, lis[i] + lds[i] - 1);
            }
        }
        
        return n - maxMountain;
    }
};

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 计算以每个位置结尾的最长递增子序列长度
        lis = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    lis[i] = max(lis[i], lis[j] + 1)
        
        # 计算以每个位置开始的最长递减子序列长度
        lds = [1] * n
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                if nums[i] > nums[j]:
                    lds[i] = max(lds[i], lds[j] + 1)
        
        # 找最长的山形子序列
        max_mountain = 0
        for i in range(1, n - 1):
            # 必须左右两边都有元素才能构成山形
            if lis[i] >= 2 and lds[i] >= 2:
                max_mountain = max(max_mountain, lis[i] + lds[i] - 1)
        
        return n - max_mountain

public class Solution {
    public int MinimumMountainRemovals(int[] nums) {
        int n = nums.Length;
        
        // 计算以每个位置结尾的最长递增子序列长度
        int[] lis = new int[n];
        Array.Fill(lis, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    lis[i] = Math.Max(lis[i], lis[j] + 1);
                }
            }
        }
        
        // 计算以每个位置开始的最长递减子序列长度
        int[] lds = new int[n];
        Array.Fill(lds, 1);
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] > nums[j]) {
                    lds[i] = Math.Max(lds[i], lds[j] + 1);
                }
            }
        }
        
        // 找最长的山形子序列
        int maxMountain = 0;
        for (int i = 1; i < n - 1; i++) {
            // 必须左右两边都有元素才能构成山形
            if (lis[i] >= 2 && lds[i] >= 2) {
                maxMountain = Math.Max(maxMountain, lis[i] + lds[i] - 1);
            }
        }
        
        return n - maxMountain;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumMountainRemovals = function(nums) {
    const n = nums.length;
    
    // 计算以每个位置结尾的最长递增子序列长度
    const lis = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                lis[i] = Math.max(lis[i], lis[j] + 1);
            }
        }
    }
    
    // 计算以每个位置开始的最长递减子序列长度
    const lds = new Array(n).fill(1);
    for (let i = n - 2; i >= 0; i--) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] > nums[j]) {
                lds[i] = Math.max(lds[i], lds[j] + 1);
            }
        }
    }
    
    // 找最长的山形子序列
    let maxMountain = 0;
    for (let i = 1; i < n - 1; i++) {
        // 必须左右两边都有元素才能构成山形
        if (lis[i] >= 2 && lds[i] >= 2) {
            maxMountain = Math.max(maxMountain, lis[i] + lds[i] - 1);
        }
    }
    
    return n - maxMountain;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
动态规划O(n²)O(n)

说明：

  • 时间复杂度：O(n²)，需要两次嵌套循环分别计算 LIS 和 LDS
  • 空间复杂度：O(n)，需要额外的数组存储 LIS 和 LDS 结果
  • 可以优化到 O(n log n) 使用二分查找计算 LIS 和 LDS，但代码复杂度会增加

相关题目