第4次 算法 & 面试 讲座单调队列单调堆栈二叉树遍历前、中、后杨氏矩阵查找快排partition及变形荷兰国旗第一个缺失的正整数陈列判别假设hash是O(1)2-sum最长无反复字符的子串字符串KMP 最长回文子串前缀相关公司普通没有本人的题库，即使有，面试官也有权本人选择问题面试胜利 = 实力 + 运气灵敏掌握，千万别背题！例1 判别括号能否合法输入只需6种字符的字符串，( ) 判别字符能否合法？左括号入栈，右左括号看栈顶？Match就出栈，否那么就错误。例2 数轴上一群鱼，从左到右的顺序知道每条鱼游动的方向正负，每条鱼的速度一样，但大小都不同，假设大小鱼相遇，小鱼被吃掉，问最后剩几条鱼？扫一遍，遇到正方向入栈，负方向出栈直到一条被吃掉或者栈为空。例3 一个队列，每次进入一个数，不断查询求最近k个数的最大值？本质：对于一个新数x，那么比它旧的且不超越它的数是没有用的。算法：假设新来一个数，把过期的扔掉，把比这个数旧的并且不超越它的数都扔掉。队列里的数是严厉单调递减的。队首永远是最大值。例如K = 2, 数字是 4,5,3,2,7,8,1新数新数队列队列4454，535, 3 4过期23，2 5过期77 3过期，2比7小88 7比8小18，1例4 给定一个数组和两个整数s=x?把数列改一下:ai = ai xsumi的定义不变：对每个sumisumi sumi t, sumi sumi- t + 1,sumi sumi s的最大值能否大于等于0?求等价于sumi-t, sumi t + 1,sumi s的最大值单调队列！算上二分的复杂度O(NlogM) 例4 直方图最大面积矩形用堆栈对每一块找到它能延伸的左右边境对每一块堆栈顶矮，这一块左边境确定，入堆栈顶高，堆栈顶右边境确定，出入栈时左边境确定出栈时右边境确定堆栈里的是递增的本质：中间的短板没有用！复杂度 O(n) 2，1，5，6，2，3 新数新数堆栈堆栈说明说明H0 =222入栈,左边界(-1)H1 = 112出栈，右边（1），1入栈，左边界(0) H2 = 55,15入栈 ，左边界（1）H3 = 66，5，16入栈，左边边界（2）H4 = 22,16，5出栈，右边界（4），2入栈左边界（1）H5 = 33,2,13入栈，左边界(4)H6 = 03,2,1,出栈 右边界（6）数据数据左右边界左右边界面积面积H0 =2（-1，1）2H1 = 1（0， 6）5H2 = 5（1，4）10H3 = 6（2，4)6H4 = 2(1,6)8H5 = 3(4,6)3普通图的遍历O(m), O(n2)树的遍历 O(n)二叉树的遍历 O(n)在遍历的时候，我们可以得到很多信息树的高度，节点最大小值，从根到该节点的数字和？例5 判别二叉树能否一样？例6 在行列都单增的矩阵里查找一个数。查找9， 15-11-7-8-9思索： 非线性 查找有几个正数？T(m * n) = T(0.75 * m * n) + O(1)例7： 荷兰国旗问题一个数组，只需0,1,2，给它排好序？循环不变式:0.p是0，q.n 1是2,p + 1.i 1是1例8 陈列判别整数数组，前往从1开场第一个不在数组中得整数？把Ai换到AAi 1的位置即可例9 2-SUM，一个数组，找到其中两个值，使其和为给定的值X。普通做法： 要排好序，两头扫。假设hash是O(1),那么2-SUM 可以在O(N)时间内处理。可以先扫一遍都扔进unordered_map,再对每个数查找一遍X ai。复杂度O(N)。例10 给定数组，选择连个下标i,j满足ai aj的前提下j i尽能够大。假设一个数左边有小于等于它的，它不能够作为i。我们可以从左到右扫一遍，同时记录左边的最小值，把可以作为i的保管下来，放入堆栈。留意堆栈的值越靠顶越小。从右向左扫瞄能够的j。弹出i。继续扫。复杂度O(n)。例如 4，3，5，2，1，3，2，3能够的i有4,3,5,2,1,3,2,3然后从右到左扫描 j，对每个j，找到尽能够左的i。堆栈里弹出的是曾经找到尽能够大的j了，所以不会再后面思索了。例11 x轴上每个位置有一棵树直向上的直线，以数值的直线为边境，中间的部分当做一个容器，问最多能盛多少水？ 两个轴位置i j留意如今一定有xj 0)表示从i开场的字符串和原串能匹配的最长前缀长度。能否O(n)求出pi?套用Manacher算法，假设p1.i 1都曾经算好了，原先框最右边境是right，该框对应的左边境是left。 我们要计算pi,1 假设right = i，即i被框住了，i的位置相当于原串的开头的什么位置？ i = i left!我们看看pi由p的定义，留意，在框内的部分i和i往后都是一样的不出框的话pi至少是min(pi,right i + 1)出框的部分暴力比较，更新right,left。同理，思索右边境，更新的次数，算法是O(n)的。weibo/cpcs 曹鹏博士cao_peng126谢谢各位！