得到山形数组的最少删除次数(LeetCode日记)

2023-12-23 14:20

本文主要是介绍得到山形数组的最少删除次数(LeetCode日记),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

题目信息:

我们定义 a r r arr arr山形数组 当且仅当它满足:

  • a r r . l e n g t h > = 3 arr.length >= 3 arr.length>=3
  • 存在某个下标 i i i (从 0 开始) 满足 0 < i < a r r . l e n g t h − 1 0 < i < arr.length - 1 0<i<arr.length1 且:
    • a r r [ 0 ] < a r r [ 1 ] < . . . < a r r [ i − 1 ] < a r r [ i ] arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[0]<arr[1]<...<arr[i1]<arr[i]
    • a r r [ i ] > a r r [ i + 1 ] > . . . > a r r [ a r r . l e n g t h − 1 ] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] arr[i]>arr[i+1]>...>arr[arr.length1]

给你整数数组 n u m s nums nums​ ,请你返回将 n u m s 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 删除一些元素后一定能得到山形数组。

相关标签 :动态规划,二分查找

题解

这道题实际上是 Leetcode 第300题 最长递增子序列 的 扩展问题。建议大家在做这道题之前可以先去了解一下上面这道题的思路和代码。下面我们开始分析本题。

方法 : 动态规划
根据题目的要求,我们需要使用最少的删除次数,使得给定的数组 n u m s nums nums 成为 山形状数组。这等价于,我们需要找出数组 n u m s nums nums 的一个最长的子序列,并且这个子序列是一个山形状数组
因此,我们可以考虑枚举山形状数组的最高点。记数组 n u m s nums nums 的长度为 n n n,并且枚举第 i i i 个元素 n u m s [ i ] nums[i] nums[i] 作为最高点,那么:

  • ( 1 ) (1) (1)在数组的前缀部分 n u m s [ 0.. i ] nums[0..i] nums[0..i] ,找出一个严格递增的子序列,并且以 n u m s [ i ] nums[i] nums[i]结束,对应着山形状数组的上升部分;
  • ( 2 ) (2) (2)在数组的后缀部分 n u m s [ i . . n − 1 ] nums[i..n−1] nums[i..n1] ,找出一个严格递减的子序列,并且以 n u m s [ i ] nums[i] nums[i]开始,对应着山形状数组的下降部分。

由于我们需要找出最长的山形状数组,并且 n u m s [ 0.. i ] nums[0..i] nums[0..i] n u m s [ i . . n − 1 ] nums[i..n−1] nums[i..n1] 这两部分是互相独立的,那么我们只需要找出 n u m s [ 0.. i ] nums[0..i] nums[0..i] 中以 n u m s [ i ] nums[i] nums[i] 结束的最长严格递增子序列,以及 n u m s [ i . . n − 1 ] nums[i..n−1] nums[i..n1] 中以 n u m s [ i ] nums[i] nums[i] 开始的最长严格递减子序列即可。

求解最长严格递增/递减子序列是一个非常经典的问题,即我们上文提到的 Leetcode 第300题 最长递增子序列 问题,使用动态规划或贪心算法的方法,可以在 O ( n 2 ) O(n^2) O(n2) 或者 O ( n l o g ⁡ n ) O(nlog⁡n) O(nlogn) 的时间内求出给定数组中,以每一个元素结尾的最长严格递增子序列的长度。
最长递增子序列问题的动态规划解法的状态转移方程如下,如果有需要的话,我可以在下一篇更新该问题。
d p [ i ] = max ⁡ 0 ≤ j < i , n u m s [ j ] < n u m s [ i ] d p [ j ] + 1 d p[i]=\max _{0 \leq j<i, n u m s[j]<n u m s[i]} d p[j]+1 dp[i]=0j<i,nums[j]<nums[i]maxdp[j]+1

对于严格递减子序列的部分,我们可以把数组 n u m s nums nums 进行反转,这样就从求解后缀的最长严格递减子序列,变成求解前缀的最长严格递增子序列了。

p r e [ i ] pre[i] pre[i] s u f [ i ] suf[i] suf[i] 分别表示上文 (1)、(2) 中找出的最长子序列的长度,只要 p r e [ i ] pre[i] pre[i] s u f [ i ] suf[i] suf[i]均大于 1,就可以拼接成一个以 n u m s [ i ] nums[i] nums[i] 为最高点的山形状数组,长度为 L = p r e [ i ] + s u f [ i ] − 1 L=pre[i]+suf[i]−1 L=pre[i]+suf[i]1,需要的删除次数为 n − L n−L nL

下面给出的代码使用了 上文提到的 最长递增子序列 问题的代码, 并将其中的代码封装成函数 g e t L I S A r r a y getLISArray getLISArray,用于求解所有的 p r e [ i ] pre[i] pre[i] ,并枚举 i i i 以得出最终的答案。

实现代码(Python)

class Solution:def minimumMountainRemovals(self, nums: List[int]) -> int:pre = self.getLISArray(nums)suf = self.getLISArray(nums[::-1])[::-1]ans = 0for pre_i, suf_i in zip(pre, suf):if pre_i > 1 and suf_i > 1:ans = max(ans, pre_i + suf_i - 1)return len(nums) - ansdef getLISArray(self, nums: List[int]) -> List[int]:n = len(nums)dp = [1] * nfor i in range(n):for j in range(i):if nums[j] < nums[i]:dp[i] = max(dp[i], dp[j] + 1)return dp
复杂度分析:
  • 时间复杂度: O ( n 2 ) O(n^2) O(n2) ,其中 n n n 是数组 n u m s nums nums 的长度。
  • 空间复杂度: O ( n ) O(n) O(n)

题记:


  • 研究生在读,我会尽量保持LeetCode每日一题的思路和代码输出。希望大家多多支持。
  • 水平有限,希望各位大佬能够批评指正。您的教诲是我进步的船帆。
  • 希望各位跟我一样的小白能跟我一起参与到做题和讨论中来。共同进步是我所能期盼的最高愿想。
  • 您的点赞和关注是我坚持分享的动力泉源,希望能将这件简单平凡的事一直做下去。感谢大家。

这篇关于得到山形数组的最少删除次数(LeetCode日记)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/528344

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return