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

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

题目描述

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

题意分析

山形数组的定义是：存在一个下标 i，使得 nums[0] < nums[1] < … < nums[i] 且 nums[i] > nums[i+1] > … > nums[n-1]，并且长度不小于 3。要求删掉最少的元素让原数组变成山形。

定义里有两个容易漏掉的硬约束。第一，两侧都是严格单调，相等的元素不能并存于同一侧。第二，峰顶两边都必须非空——i 不能是 0 也不能是末尾，所以纯递增或纯递减的数组不算山形，长度也因此至少是 3。

只允许删除、不允许移动，说明剩下的元素必须保持原有相对顺序。于是「删到山形」等价于「在原数组里挑出一个山形子序列」，而「删得最少」等价于「挑出的山形子序列最长」。答案就是 n 减去最长山形子序列的长度。

一旦把目标翻成「最长山形子序列」，结构就清楚了：任何一个山形子序列都由一个峰顶、一段严格递增的左半和一段严格递减的右半拼成，而且峰顶把它一刀两断——左半只用到峰顶左侧的元素，右半只用到右侧的元素，两边的选择互不干扰。

数据规模是数组长度不超过 1000。这个量级明确允许 $O(n^2)$，出题人期待的正是「枚举峰顶 + 两侧各做一次经典子序列 DP」，而不必上二分优化。

边界包括：数组本身已是山形（答案 0）；数组严格递增或严格递减（无合法峰顶，但题目保证至少存在一个山形，可以不特判无解）；以及大量重复元素导致某些位置无法当峰顶。

解法：LIS + LDS 合并

核心思路

删除元素不会改变相对顺序，因此最少删除等价于保留一个最长山形子序列，答案是数组长度减去该子序列长度。

固定下标 i 为峰顶，左右两侧可以独立求最优：

  • inc[i]：以 nums[i] 结尾的最长严格递增子序列长度；
  • dec[i]：以 nums[i] 开始、向右严格递减的最长子序列长度。

转移分别枚举峰顶左侧和右侧更小的元素：

\[inc[i]=1+\max_{j<i,\ nums[j]<nums[i]}inc[j]\] \[dec[i]=1+\max_{j>i,\ nums[j]<nums[i]}dec[j]\]

没有合法转移时状态为 1。只有 inc[i] > 1 且 dec[i] > 1，峰顶两侧才都非空；以 i 为峰的长度为 inc[i] + dec[i] - 1。

任意山形子序列都有唯一峰顶，其左右段不会长于对应状态；反过来，两侧最优子序列只共享峰顶，拼接后严格先增后减。因此枚举所有合法峰顶可得到全局最长山形子序列。

解题步骤

  1. 将 inc、dec 全部初始化为 1。
  2. 从左向右计算 inc，只从值严格更小的左侧位置转移。
  3. 从右向左计算 dec，只从值严格更小的右侧位置转移。
  4. 枚举 inc[i] > 1 && dec[i] > 1 的峰顶，更新最长山形长度。
  5. 返回 n - best。

对 [2,1,1,5,6,2,3,1]，得到 inc = [1,1,1,2,3,2,3,1]、dec = [2,1,1,3,3,2,2,1]。峰顶 6 对应长度 3+3-1=5，所以最少删除 3。

重复值必须使用严格比较。[1,2,2,1] 不能把两个 2 放在同一坡面，最长合法山形长度为 3。

代码实现

import java.util.Arrays;

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)$，左右两个 DP 都枚举一对下标。
  • 空间复杂度：$O(n)$，使用两个长度为 n 的状态数组。

关键点总结

  • 最少删除等于总长度减去最长合法山形子序列长度。
  • 两个状态都必须绑定同一峰顶 i，不能使用普通前缀 LIS 最大值。
  • 左右转移都使用严格小于，相等元素不能构成坡面。
  • inc[i] > 1 && dec[i] > 1 保证峰顶两侧均非空。
  • 合并长度要减去重复计算的一次峰顶。

易错点总结

  • 用 <= 转移会把相等元素放到坡面上；[1,2,2,1] 必须删除一个 2。
  • 漏掉任一侧长度大于 1 的检查，会把纯递增或纯递减子序列当成山形。
  • dec 必须从右向左计算，否则依赖的右侧状态尚未完成。
  • 合并时不减 1 会把峰顶计算两次，使删除数少一。
  • 把 inc[i] 定义成前缀最大值，会得到不一定以 i 结尾的序列，无法与右侧拼接。
  • 最终返回的是 n - best，不是最长山形长度本身。

相似题目

题目 难度 考察点
941. 有效的山脉数组 简单 只需一趟双指针验证形状，不涉及子序列选择，是山形定义的最直接考查
852. 山脉数组的峰顶索引 中等 保证已是山形，用二分找峰顶，考点从构造转为在单峰上利用单调性
300. 最长递增子序列 中等 本题左半部分的原型，掌握它的 $O(n^2)$ 与 $O(n \log n)$ 两套写法是前置条件
845. 数组中的最长山脉 中等 要求山脉是连续子数组而非子序列，因此用双指针扩展即可，$O(n)$ 解决
376. 摆动序列 中等 同样是「上升段与下降段交替」的子序列，但允许多个峰谷，贪心即可无需 DP
673. 最长递增子序列的个数 中等 在 LIS 的基础上额外维护计数状态，展示同一转移骨架如何承载第二维信息
1095. 山脉数组中查找目标值 困难 山形结构下的三次二分，且访问次数受限，考点完全在交互与边界而非 DP
1218. 最长定差子序列 中等 转移条件从「比大小」换成「差值固定」，可用哈希表把 $O(n^2)$ 压到 $O(n)$