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

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 微软
标签
数组 动态规划 二分查找 贪心

题目描述

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

image-20260929090822932

image-20260929090823030

题意分析

删除元素后，剩余元素的相对顺序不变，需要形成严格先增后减的山形序列，峰顶两侧都至少有一个元素。最少删除等价于保留最长的山形子序列，最后用原长度减去保留长度。

解法：LIS + LDS 合并

核心思路

[!blue]
固定下标 i 为峰顶，把问题拆成左右两段：inc[i] 表示以 nums[i] 结尾的最长严格递增子序列长度，dec[i] 表示从 nums[i] 开始向右的最长严格递减子序列长度。两个状态都必须包含并固定在当前位置。

每个位置单独成序列时长度为 $1$。计算 inc[i] 时，枚举 j < i 且 nums[j] < nums[i] 的前驱，把 nums[i] 接到其后，取最大的 inc[j] + 1；从左往右计算，所需状态都已完成。计算 dec[i] 时，枚举 j > i 且 nums[j] < nums[i] 的后继，取最大的 dec[j] + 1，因此要从右往左计算。

只有 inc[i] > 1 且 dec[i] > 1，峰顶两侧才都有元素。此时左侧最优序列的下标都不超过 i，右侧最优序列的下标都不小于 i，两者只共享峰顶，可以直接拼接，长度为 inc[i] + dec[i] - 1。

任意山形子序列都有一个峰顶，它的左右长度不会超过对应的两个状态；而两个状态的最优序列又确实可以拼成合法山形。因此枚举全部合法峰顶并取最大长度，就得到全局最优保留方案。题目保证删去一些元素后能形成山形，最终一定能找到合法峰顶。

解题步骤

  1. 两个长度数组初始化为 1。
  2. 从左向右求每个位置的递增长度。
  3. 从右向左求每个位置的递减长度。
  4. 枚举合法峰顶，求最长山形并返回 n-best。

两个方向都使用严格小于，相等元素不能直接连接到同一单调段。原数组本身已经是山形时，最长保留长度就是 $n$，删除数为 $0$。

代码实现

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] inc = new int[n];
        int[] dec = new int[n];

        Arrays.fill(inc, 1);
        Arrays.fill(dec, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    inc[i] = Math.max(inc[i], inc[j] + 1);
                }
            }
        }

        // 右侧状态先完成，求以当前位置开始的严格递减长度。
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[i]) {
                    dec[i] = Math.max(dec[i], dec[j] + 1);
                }
            }
        }

        int best = 0;

        for (int i = 1; i < n - 1; i++) {
            // 峰顶两侧都要非空，合并后减去重复计数的峰顶。
            if (inc[i] > 1 && dec[i] > 1) {
                best = Math.max(best, inc[i] + dec[i] - 1);
            }
        }

        return n - best;
    }
}

func minimumMountainRemovals(nums []int) int {
    n := len(nums)
    inc := make([]int, n)
    dec := make([]int, n)
    for i := range nums {
        inc[i], dec[i] = 1, 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] && inc[j]+1 > inc[i] {
                inc[i] = inc[j] + 1
            }
        }
    }

    // 右侧状态先完成，求以当前位置开始的严格递减长度。
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[i] && dec[j]+1 > dec[i] {
                dec[i] = dec[j] + 1
            }
        }
    }

    best := 0
    for i := 1; i < n-1; i++ {
        // 峰顶两侧都要非空，合并后减去重复计数的峰顶。
        if inc[i] > 1 && dec[i] > 1 {
            length := inc[i] + dec[i] - 1
            if length > best {
                best = length
            }
        }
    }
    return n - best
}

复杂度分析

  • 时间复杂度：$O(n^2)$，两个方向各枚举下标对，最后再线性枚举峰顶。
  • 空间复杂度：$O(n)$，保存两组长度。

关键点总结

[!green]

  • 两个状态分别以当前下标为终点和起点。
  • 两侧必须严格单调，重复值不能直接接上。
  • 合并时峰顶重复一次，需要减一。

易错点总结

[!yellow]

  • 把 inc 定义成整个前缀的最长值：得到的序列未必以当前峰顶结束。
  • 漏掉两侧长度大于一的条件：可能把单调序列算成山形。
  • 递减状态从左向右算：所需的右侧状态还没完成。
  • 返回 best：题目要删除数，应返回 n-best。

相似题目

题目 难度 关联与区别
300. 最长递增子序列 中等 分别计算每个位置左侧LIS与右侧下降链，选择两边都非空的峰得到最长可保留山形。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/71128228
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！