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

本文主要是介绍2023-12-22 LeetCode每日一题（得到山形数组的最少删除次数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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] <= 10⁹
题目保证 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;}
};