学习笔记

11. 盛水最多的容器 双指针从两侧向中间移动，哪边的值小移动哪边指针，每次移动计算面积并更新最大值。 只有移动大值指针会让面积更小，因此移动小值指针才有可能找到更大值。 利用双指针夹逼法，是处理数组问题的一种常见方式。主要利用指针移动后，可以让问题解逐渐收敛的场景。

12. 三数之和 首先排序成有序数组，然后固定最左侧数字，在右侧序列中查找满足条件的两个数。 问题转化为，利用双指针夹逼法，使解空间不断收敛的问题。 是双指针求解问题的变种

13. 有效的括号 子问题解对称，典型的利用栈空间求解问题。 遇到左括号入栈，遇到右括号，与栈顶元素比较并出栈。

14. 合并两个有序链表 依次比较两个链表头节点，并从依次出旧链，入新链。 关键点： 初始时新链表头添加一个多余辅助节点，可令程序处理更简洁。 初始时记录下头指针供后面结果返回

70 爬楼梯 问题可抽象为斐波那契数列 f(n) = f(n-1)+f(n-2) 求解斐波那契数列的方法有：

1. 普通的递归求解 求解过程中包含大量重复计算，递归分解过程是一颗递归树，每次一分为2，时间复杂度为O(2^k),k为递归树高度，十分耗时。
2. 缓存中间结果的递归求解 将子问题的计算结果记录到哈希表，每次求解时，先查表，找不到结果再计算，这样时间复杂度为O(n)，同时哈希表增加了空间复杂度
3. 利用循环求解(最优解) 可将问题转化为自底向上的循环问题: f3=f2+f1,f1=f2,f2=f3, 时间复杂度O(n),空间复杂度O(1)