题目

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

arr.length >= 3 存在某个下标 i （从 0 开始） 满足 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 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。

提示：

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

思路

两个LIS 随后遍历找最小

解法

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        var inc = new int[n];
        var dec = new int[n];
        Arrays.fill(inc, 1);
        Arrays.fill(dec, 1);
        for (int i = 1; i < n - 1; 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 - 2; i > 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    dec[i] = Math.max(dec[i], dec[j] + 1);
                }
            }
        }
        int ans = 0x3f3f3f3f;
        for (int i = 1; i < n - 1; i++) {
            if (inc[i] == 1 || dec[i] == 1)
                continue;
            ans = Math.min(ans, n - inc[i] - dec[i] + 1);
        }
        return ans;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现