2023-12-22 LeetCode每日一题(得到山形数组的最少删除次数)

2024-01-01 06:26:21

2023-12-22每日一题

一、题目编号

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

二、题目链接

点击跳转到题目位置

三、题目描述

我们定义 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:
在这里插入图片描述

示例 2:
在这里插入图片描述
提示:

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

四、解题代码

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre = getLISArray(nums);
        vector<int> suf = getLISArray({nums.rbegin(), nums.rend()});
        reverse(suf.begin(), suf.end());

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

        return n - ans;
    }

    vector<int> getLISArray(const vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }
};

五、解题思路

(1) 类似于最长递增子序列。

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