• 复杂度总结

• 数组是一串连续内存地址空间，可支持下标动态访问，一维数组的寻址公式如下：

a[i]_address = base_address + i * data_type_size

• 和数组相比，链表更适合插入、删除操作频繁的场景。常用的链表还有双向链表、循环链表、双向循环链表。
• 栈可以用于保存特定顺序的数据，比如单调递增数据、单调递减数据、对称数据等等。另外，各种语言中的函数调用也是使用的栈形式，简称函数栈，因为调用符合后进先出的特性。

（好久不用Java了，一点小小的分析，有错误请帮忙指出，谢谢~）

Queue位于java.util包，在Java中是一个接口，继承于集合Collection，提供了插入（add和offer）、删除（remove和poll）、检查（element和peek）三类接口，各自分别包含两个方法，前者在队空或者队满时直接抛出异常，后者直接返回一个默认值。

另外，还有四个继承于Queue的子接口，包含双向队列、阻塞双向队列、阻塞队列、传输队列。而基于队列实现的类有很多，比如顺序队列、链式队列、并发队列、阻塞队列、优先队列等等。

Java中的优先队列使用最小堆实现。

优先队列的构造器有两个可调节参数，分别是初始空间大小initialCapacity和比较器comparator，如果不指定初始空间大小，那默认的空间大是11；如果不指定比较器，那默认会使用元素的自然顺序Comparable natural ordering作为比较器。除此之外，优先队列还可以从其他集合Collection进行初始化，比如有序集合、其他优先队列、其他集合等等，从其他集合初始化的优先队列，会将其他集合的元素copy过来，然后使用给定或默认的比较器构建最小堆，从而完成优先队列的初始化。

优先队列的插入方法为add和offer，其中add方法直接调用了offer方法。插入操作首先检查插入元素，如果元素不可比较，则会抛出异常。然后会检查队列空间，如果空间不足则会自增长空间。如果原始空间小于64个元素时，则每次增加2个新元素空间；如果超过64，则每次队列空间翻一倍。然后就会将插入的元素交给比较器，插入到最小堆中。整个插入的时间复杂度在最小堆处，即为O(log(n))。

检索方法为peek，直接返回已经排好序的优先堆中的第一个元素，即队列的第一个元素，如果是默认的比较器，那该元素是最小的元素。时间复杂度为O(1)。

删除方法有两个，分别是remove和poll方法，两者的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护最小堆的性质，需要进行必要的调整。另外，remove方法直接删除指定数值的第一个元素，而poll是移除并返回出队列第一个元素，remove方法会先查找需要删除元素第一次出现的位置，如果是最底层的元素，那直接删除即可，如果是中间或顶部的元素，则需要删除后重新构建最小堆，构建的复杂度为O(log(n))。但是remove方法有一次遍历查找的过程，所以时间复杂度为O(n)，而poll方法为O(log(n))。

另外，还有是否包含contains的方法，clear清空的方法，其复杂度都是O(n)。

至于最小堆部分的代码，就等学习堆的时候再进行分析吧。

总结了一下这周几道题的方法（套路）。

• 哈希表

  利用空间换时间，可以达到O(1)的查询速度。往往在多重循环中，可以将其中一层替换为哈希表查找，从而实现时间复杂度的降维。

  本周代表题目是1.两数之和、141.环形链表。

• 栈（单调栈）

  栈用得最多的也就是单调栈，另外老师讲的对称结构用栈解决也可以。单调栈往往出现在往后遍历过程中，同时有需要不断向前望，找到合适的元素，这个时候单调栈常常会发挥作用。暂时还不太熟，单调栈的题目需要先理清思路，常常会比较绕，还需要多多练习。

  本周栈类型题目：20. 有效的括号、84. 柱状图中最大的矩形、42. 接雨水

• 双指针

  双指针可能是在数组中使用最多的技巧了，有时候还会涉及三指针、四指针，用于减少遍历次数。双指针主要包含两种，第一种是快慢指针，主要解决链表中的问题，比如环形链表、链表中点，寻找链表倒数第K个元素等等；第二种是左右指针，主要解决数组或字符串的问题，最常见的就是二分查找问题。左右指针分别从左右遍历数组，按一定规则进行元素比较，从而实现某种目的。左右指针可以常练习一下，多掌握一下其规则。

  本周双指针类型题目：11. 盛最多水的容器、15. 三数之和、42. 接雨水、141.环形链表、142. 环形链表 II、189. 旋转数组、239. 滑动窗口最大值

• 哨兵

  哨兵是一种简化边界处理的技巧，可以让程序省略更多判断，更加简洁易懂。这种技巧尤其是在插入排序中用得最多。

  本周典型题目：84. 柱状图中最大的矩形

• 递归

  递归其实说白了就是我们的数学归纳法，从第n项逐渐反向推至第一项。这里大概总结一下递归的三个要素：

  • 明确函数的功能和目的
  • 寻找递归的终止条件，比如循环到1时返回其本身
  • 找出递推公式

  另外，递归还有一点需要注意的，尽量避免重复计算，把计算过的值可以保存起来。特别是某些语言，如果函数栈过深，很容易导致堆栈溢出。典型重复计算的题目包括求解斐波拉契数值、爬楼梯等。

  本周递归的典型题目：21.合并两个有序链表、70. 爬楼梯、206. 反转链表

• 动态规划

  暂时还不太理解，先空着，之后再来总结。本周代表型题目：42.接雨水

除了上述解题套路以外，还是有一些小技巧可以使用的，就比如滚雪球大法等，另外一些就涉及常规的数组的常规操作了，比如数组元素的移动、插入、复制、交换等等。用好这些技巧就可以大大节省程序的运行时间，总之，尽量避免暴力求解，多考虑一些数组元素的内部规律。有时候可以自己手动画图进行思考，手动画图遍历一个个的元素，画出他们需要怎么移动、操作之类的。

最后，一点提醒自己的，注意边界和特例的问题。