leetcode编程算法随笔(难度2608 懒删除堆 双向链表 抄写法以及其它)-移除最小数对使数组有序 II

#懒删除堆 (就是在堆中数据弹出的时候,额外判断一下这个数据是否"有效")

#也就是优先队列

#双向链表

#两个有序集 (c++的set , python的SortedList)

#抄写法

1. 2608的难度分,差不多属于'一眼放弃'的难度,于是想起了有位大家的方法是抄写,尝试一下. 有以下几个小经验:

1.0 先试着用自己的办法看看哪里走不通了. 

本例,朴素模拟是容易想到的,但时间复杂度会是O(n²)

那么,如何降低复杂度呢？

对于每次操作之后,重新找最小的和,是不是可用堆优化呢?

以及判断非递减是否可以优化？

1.1 抄写的东西难度,还是要在当前知识与理解的边缘.

1.2 先尝试理解每一句(代码行), 保证局部理解后,再去理解整体.

1.3 尝试将过程中的指涉关系清晰,全面,整体.

#这个问题,总能让自己想起,#智力是否可以提高

2. 写法一  

优先队列(堆) + 双向链表

关键点1,堆中每一项存放什么数据是够用? 

# 两个元素的和,与它们各自的索引就够了

关键点2, 当堆弹出项后,一个元素后, 会有哪些变化?

不要急,慢慢分析, 来个辅助图

当从堆中取出一个项, 意味着有两个数要合并，因为它们是满足条件的最小值。

对原数组，删掉了一个数值，修改了一个数值。而同时，

堆中有两个项已经失效了(5,6),但也产生了两个新的(6,8)

#在边界的时候特殊处理 

如何记录失效的项, 以及如何正确的加入新的项?

加上索引, 就清晰了,如果堆中的某个项的两个索引中任一个参与过合并,它就是失效的, 一个数组就可以记录,修改与查询也不会有大的时间消耗.

代码一

1. 定义双向列表的节点

2.定义堆中项,主要是定义如何比较