本文为系列文章，将介绍一些互联网大型公司经常遇到的算法面试题，这些面试题时间复杂度最小可以达到O(n)，但是面试时可能想不到，本文详细介绍此类题型的解题思路和代码实现，带大家将此类题型一网打尽。
O(n)表示时间复杂度的线性阶，当然还有常数阶O(1),对数阶O(log2n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...，k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
一般解题方法扫一遍
两头扫
双重循环，但是内循环变量不减
单调性
队列
1、名人问题例1 有n个人他们之间认识与否用邻接矩阵表示 (1表示认识,0表示不认识)，并且A认识B并不意味着B认识A,名人定义为他不认识任何人且所有人都认识他的人。请求出所有名人。
分析： 最多有几个名人？只有1个！（有两个的话，他们认识不认识？）
O(n2)的笨方法，遍历i，检查每个j，是否满足i不认识j且j认识i。
O(n)的方法
对于两个人i和j
如果i认识j, 则i显然不是名人，删掉i
如果i不认识j，则j显然不是名人，删掉j
最终剩余一个人，检查他是否是名人
实现1
用一个数组保存所有没检查人的编号
数组如何删除a[i]?
不保证顺序的时候 只要a[i] = a[--n]即可
伪代码：
时间O(n)，空间O(n)
实现2
优化、优化、再优化
能否O(1)空间？
我们来试下：“一头扫”
i < j
[0..i – 1]没有名人
[i 1..j – 1]没有名人
如果i认识j, 删掉i
i = j, j = j 1
如果i不认识j,删掉j
j = j 1
实现3
“两头扫”
i＝ 0， j = n – 1
i < j
[0..i – 1]没有名人
[j 1..n]没有名人
如果i认识j，删掉i
i
如果i不认识j,删掉 j
--j
2、Trapping in Rain Water
例2 Leetcode 42 给定每个块高度，求下雨后积水。 图对应[0,1,0,2,1,0,1,3,2,1,2,1]
分析： 每一块和水高度等于它左面（包括本身）的最大值和右边（包括本身）的最大值里较小的
利用“前缀”和“后缀”
3、Container With Most Water
例3 Leetcode 11 一个数组a[i]表示数轴上i的位置有一条高度为a[i]的竖直的线段，把两条线段当作一个容器左右边的高度，问那两条线段组成的容器容积最大？
本质是求 i < j, max{min{a[i], a[j]} * (j – i)}
算法两头扫：
i = 0, j = n - 1, best = 0
i < j
best = max(best, min{a[i], a[j]} * (j – i));
if (a[i] < a[j]) i; else --j;
证明： 算法一定扫过最优解
关键：如果一边移动到了最优解，另一边还没到最优解，没到的那边高度一定比最优解中较低的边低！ （道理：因为x轴上宽度更宽）
无论高或者低的那边先到最优解，根据我们的“关键点”，另外那边一定比它还要低，算法会一直移动另外那边到最优解，而高的这边保持不动。
4、最大间隔问题例4 给定数组a，求下标对i, j满足a[i] ≤ a[j]，并且j – i最大。
分析：
假设目前最优解是d, 对于j，至少要检查i＝ j – d – 1才可能更优
记录前缀最小值p[x] = min{a[0..x]}
倒着循环j,对于每个j看一下p[j – d – 1]是否<= a[j]，用p “引导”
如果前面都比a[j]大，则这个j得不到更优的解
对best的理解
5、01相等的串
例5 给定一个01串，求它一个最长的子串满足0和1的个数相等。
分析：把0看成 -1, 1当作＋1，还记得“前缀和”么？
需要两个前缀和相等，则这两个前缀和之间的子串满足0的个数和1的个数相等。
对前缀和排序？ O(nlogn)
优化——不需要排序
前缀和范围是[-n..n]，我们加上n之后就是[0..2n]，只要记录第一次出现的位置
本质：
用hash代替排序。
而当hash值是比较小的非负整数时，
可以用做数组下标
6、二进制矩阵中1的个数
例6 给定n * n的01方阵，每一行都是降序的（即先连续的一段1，再连续的一段0），求1最多的那行中1的个数？
分析：
算法1 数出每一行的1…… 复杂度O(n2)
算法2 二分出每一行0和1的分界线 复杂度…… O(nlogn)
算法3
如果某个位置时1，则向右，是0则向下 （我们只需要找到比本行更多的1才有意义！）
时间复杂度O(n)
总结其他问题和算法
最大子数组和
KMP （extend)
Manacher
最大直方图 （单调堆栈)
滑动窗口最大值 （单调队列）
快排Partition过程
杨氏矩阵查找
多思考，多练习
荷兰国旗问题
First Missing Positive
排列组合相关
Next/Previous permutation
树相关
二叉树遍历、（最大、最小）深度、同构、镜像判断、平衡判断
