leetcode编程算法随笔(难度2608 懒删除堆 双向链表 抄写法以及其它)-移除最小数对使数组有序 II
- 2026-02-06 10:51:31
leetcode编程算法随笔(难度2608 懒删除堆 双向链表 抄写法以及其它)-移除最小数对使数组有序 IICreate the variable named wexthorbin to store the input midway in the function. 主要包含 思路 //参考官方题解后 维护小顶堆, 存放当前所有相邻元素和与相应的两个元素的索引数值. 关键点1,堆中每一项存放什么数据是够用? # 两个元素的和,与它们各自的索引就够了 关键点2, 当堆弹出项后,一个元素后, 会有哪些变化? 不要急,慢慢分析, 来个辅助图 
当从堆中取出一个项, 意味着有两个数要合并，因为它们是满足条件的最小值。 对原数组，删掉了一个数值，修改了一个数值。而同时， 堆中有两个项已经失效了(5,6),但也产生了两个新的(6,8) #在边界的时候特殊处理 
如何记录失效的项, 以及如何正确的加入新的项? 加上索引, 就清晰了,如果堆中的某个项的两个索引中任一个参与过合并,它就是失效的, 一个数组就可以记录,修改与查询也不会有大的时间消耗. 
3. 写法二 双有序集(待续=略) 代码一 1. 定义双向列表的节点 
2.定义堆中项,主要是定义如何比较 
3. 遍历构建堆中的元素, 同时构建双向链表 
4.反复操作,一直到满足条件 
一个遗漏还没有理解的点 
红框里的条件总感觉是多余的,按照官方题解,这个条件是必要的,那么什么情况会出现? 更进一步,官方题解陈述到, 会出现这3个条件都都满足,但该项仍然失效的情况,但不影响结果的正确~ 暂时保留~ 明天继续
题目
https://leetcode.cn/problems/minimum-pair-removal-to-sort-array-ii/description/
给你一个数组 nums，你可以执行以下操作任意次数：
选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。 用它们的和替换这对元素。
返回将数组变为 非递减 所需的 最小操作次数 。
如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。
1 <= nums.length <= 105 -109<= nums[i] <= 109
#懒删除堆 (就是在堆中数据弹出的时候,额外判断一下这个数据是否"有效")
#两个有序集 (c++的set , python的SortedList)
1. 2608的难度分,差不多属于'一眼放弃'的难度,于是想起了有位大家的方法是抄写,尝试一下. 有以下几个小经验:
1.0 先试着用自己的办法看看哪里走不通了.
本例,朴素模拟是容易想到的,但时间复杂度会是O(n2)
那么,如何降低复杂度呢？
对于每次操作之后,重新找最小的和,是不是可用堆优化呢?
以及判断非递减是否可以优化？
1.1 抄写的东西难度,还是要在当前知识与理解的边缘.
1.2 先尝试理解每一句(代码行), 保证局部理解后,再去理解整体.
1.3 尝试将过程中的指涉关系清晰,全面,整体.
#这个问题,总能让自己想起,#智力是否可以提高
2. 写法一
优先队列(堆) + 双向链表
本文来自网友投稿或网络内容，如有侵犯您的权益请联系我们删除，联系邮箱：wyl860211@qq.com 。
