【教3妹学编程-算法题】得到山形数组的最少删除次数

2023-12-22 10:29:43

瑟瑟发抖

3妹:好冷啊, 冻得瑟瑟发抖啦
2哥 : 这波寒潮影响20个省,上海也是近年来的最低温了, 外面风吹的呼呼的。
3妹:这么冷的天,不想上班!
2哥 : 我看到外面竟然有的女生还穿裙子,大腿都露在外面,难道她们不怕冷的吗?
3妹:她们穿了光腿神器,2哥真是老土!
2哥:啊,这样啊,那真的。还有,再冷的天也别忘记刷题啊。
3妹:好的,我要上班去了,你发我微信上,我通勤路上看一下~

吃瓜

题目:

我们定义 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 删除一些元素后一定能得到山形数组。

思路:

思考

动态规划,
根据题目的要求,我们需要使用最少的删除次数,使得给定的数组 nums成为「山形状数组」。这等价于,我们需要找出数组 nums 的一个最长的子序列,并且这个子序列是一个「山形状数组」。

因此,我们可以考虑枚举「山形状数组」的最高点。记数组 nums 的长度为 n,并且枚举第 i 个元素 nums[i]作为最高点。详解如代码:

java代码:

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] pre = getLISArray(nums);
        int[] reversed = reverse(nums);
        int[] suf = getLISArray(reversed);
        suf = reverse(suf);

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (pre[i] > 1 && suf[i] > 1) {
                ans = Math.max(ans, pre[i] + suf[i] - 1);
            }
        }

        return n - ans;
    }

    public int[] getLISArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }

    public int[] reverse(int[] nums) {
        int n = nums.length;
        int[] reversed = new int[n];
        for (int i = 0; i < n; i++) {
            reversed[i] = nums[n - 1 - i];
        }
        return reversed;
    }
}

文章来源:https://blog.csdn.net/kangbin825/article/details/135145786
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。