Skip to content

Latest commit

 

History

History
109 lines (63 loc) · 4.08 KB

3041.maximize-consecutive-elements-in-an-array-after-modification.md

File metadata and controls

109 lines (63 loc) · 4.08 KB

题目地址(3041. 修改数组后最大化数组中的连续元素数目 - 力扣(LeetCode))

https://leetcode.cn/problems/maximize-consecutive-elements-in-an-array-after-modification/

题目描述

给你一个下标从 0 开始只包含  整数的数组 nums 。

一开始,你可以将数组中 任意数量 元素增加 至多 1

修改后,你可以从最终数组中选择 一个或者更多 元素,并确保这些元素升序排序后是 连续 的。比方说,[3, 4, 5] 是连续的,但是 [3, 4, 6] 和 [1, 1, 2, 3] 不是连续的。

请你返回 最多 可以选出的元素数目。

 

示例 1:

输入:nums = [2,1,5,1,1]
输出:3
解释:我们将下标 0 和 3 处的元素增加 1 ,得到结果数组 nums = [3,1,5,2,1] 。
我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ,是连续元素。
最多可以得到 3 个连续元素。

示例 2:

输入:nums = [1,4,7,10]
输出:1
解释:我们可以选择的最多元素数目是 1 。

 

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106

前置知识

  • 动态规划

公司

  • 暂无

思路

1218. 最长定差子序列 类似,将以每一个元素结尾的最长连续的长度统统存起来,即dp[num] = maxLen 这样我们遍历到一个新的元素的时候,就去之前的存储中去找dp[num - 1], 如果找到了,就更新当前的dp[num] = dp[num - 1] + 1, 否则就是不进行操作(还是默认值 1)。

由于要求排序后连续(这和 1218 是不一样的),因此对顺序没有要求。我们可以先排序,方便后续操作。

另外特别需要注意的是由于重排了,当前元素可能作为最后一个,也可能作为最后一个的前一个,这样才完备。因为要额外更新 dp[num+1], 即 dp[num+1] = memo[num]+1

整体上算法的瓶颈在于排序,时间复杂度大概是 $O(nlogn)$

关键点

  • 将以每一个元素结尾的最长连续子序列的长度统统存起来

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def maxSelectedElements(self, arr: List[int]) -> int:
        memo = collections.defaultdict(int)
        arr.sort()
        def dp(pos):
            if pos == len(arr): return 0
            memo[arr[pos]+1] = memo[arr[pos]]+1 # 由于可以重排,因此这一句要写
            memo[arr[pos]] = memo[arr[pos]-1]+1
            dp(pos+1)
        dp(0)
        return max(memo.values())

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:$O(n)$

相关题目

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。