作者：左程云
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
程序员代码面试指南：IT名企算法与数据结构题目最优解试读：
特别说明
1．本书所有题目的代码都为Java实现，但这并不会妨碍其他语言使用者的阅读。这是因为笔者在实现每一道题目时，都尽最大努力回避与Java语言特性相关的写法出现，而且尽量遵循大多数编程语言共有的写法习惯。所以，将本书中的Java实现改写成其他语言的实现是非常容易的。
2．在Java中，如果想得到字符串str第i个位置的字符，需用如下方式：
char p=str.charAt(i);
本书提供的函数中有大量参数为字符串类型的函数，但如上所示的方式并不符合大多数读者的阅读习惯。为了让代码更加易读，笔者都在这样的函数中把字符串类型的参数转换成char类型数组的变量来使用，例如：
char[] charArr=str.toCharArray();
此时得到字符串str第i个位置的字符，可以用如下方式：
char p=charArr[i];
在本书中，发生如上转换行为的函数在估算额外空间复杂度的时候，笔者并没有把charArr的空间计算在内，这是因为如果不转换成char数组，而是选择直接使用原参数str，也是完全可以的，之所以选择转换，仅仅是为了让读者更容易读懂代码；是否进行转换对算法的逻辑没有任何影响，所以不把charArr的空间算作必须使用的额外空间。
另外，本书涉及的程序源代码可以在http://www.broadview.com.cn/27011中下载。
推荐序1
2015年春节，因为公司业务的快速发展，我们开始寻觅优秀的笔试面试算法讲师。几经周折，找到了当时在举办线下算法分享的程云，认认真真地听他讲了一堂课，当时就认定他就是我们要找的人。
我听过很多国内顶尖ACM选手的算法分享，但是每一次听完以后总觉得我和那些人永远隔着一个断裂带，算法对我来说遥不可及，而程云讲解算法的时候总能从最小的切口讲起，由浅入深，环环相扣，不知不觉引你走向算法的核心精髓，那种醍醐灌顶的感觉能激发大家学习算法的热情，并一直推着我们前进。
这几年IT技术蓬勃发展，日新月异，对技术人才的需求日益增长，程序员招聘市场也如火如荼。在有限的三五轮面试中，国外流行让面试者编程解决某些数据结构和算法的题目，通过观察面试者编码的熟练程度、思考的速度和深度来衡量面试者的能力和潜力。国内以百度、阿里、腾讯为首的互联网企业也都逐步开始采用算法面试来筛选人才。
程云出于对算法的热爱，长期泡在careercup、leetcode等笔试面试网站上，编码解决各种最新的笔试面试编程题，对各种笔试面试编程题的解题技巧了如指掌。
算法面试普及后，传统的数据结构和算法课本讲得太过基础，又远离求职需求，国内也逐渐出现迎合求职需求的笔试面试工具书，这些书籍有些过于应试，纯粹以通过面试为导向，程云的书和那些书相比，题目更前沿，讲解更注重思考思路和代码的实践技巧，对每个题目都深挖最优解，同时根据自己在线下讲课学员们的反馈，对每个编程考题的解题反复修改，让思路更清晰。
这本书不仅可以作为面试代码指南，还可以作为学生课后的辅助练习，“刷”题5年，悉数总结都沉淀在这本书里，相信读者跟着他的引导从头到尾逐一攻克一定会有所收获。叶向宇牛客网CEO
推荐序2
初次遇见程云是在2014年8月，当时我在上一家公司工作刚好满4年，也是在那时我开始想换个环境，寻找新机会，就试着投了一家公司，结果第一次面试遇到算法题就被淘汰了。后来又面试过其他一些国内互联网公司，也总是卡在算法上。其实，之前我曾经自己在家抱着《算法导论》“啃”了几章，花了1个月的业余时间看了前5章，后面就没再继续坚持下去。看过的人都知道，虽然很有用，但实在很难“啃”。
单调地看书很枯燥，于是想到去网上找志同道合的人一起研究，就开始“逛”算法论坛。很巧的是，在某个论坛的算法板块看到一个帖子，说是在周末有算法交流班，当时我立即报名，周日的名额已满，我是很幸运地“替补”上去的。
还记得第一次交流是在程云租的房子里，小小的客厅里放了一张沙发、两排椅子和一张桌子，桌上放着笔记本电脑和一台大电视，前面还挂着白板。第一次算法交流就在这样的环境里开始了。
程云讲起题来犹如行云流水，我们听得更是酣畅淋漓，第一次听完就爱上了……当然，我说的是他的讲述。
相信大家都有过这样的经历，面对一道算法题，苦思冥想了半天，还是不知道怎么解，感觉很沮丧。如果这时突然有人把解题思路和方法以及代码都告诉你了，是不是感觉豁然开朗，心情舒畅了？这样的情景一天出现一次就可以让人感觉很开心，而如果一天连续出现二十次，那将会是什么感觉？一个字：爽！
程云把每一道题都讲解得清晰透彻，有的题目难以理解、思路诡异，他就会不厌其烦地反复讲解，用形象的方式展现复杂的逻辑，直到大家都听懂为止。给人的感觉可以说是高潮迭起，一波又一波。
后来进行第二次交流时，我带来最好的朋友一起参加。之后的交流中，我和朋友都毫不犹豫地报名参加。交流的内容涉及经典算法的高难度题目，也有一些小巧玲珑的技巧题。难题难得让人叹服，巧题巧得让人玩味。
对想去国外大公司就职的程序员来说，算法题这一关是必不可少的。程云讲述的题目是他5年“刷”题的经验积累而成的，其实只要掌握题目的解题思路和思想，就足以应付国内互联网公司程序员职位的算法面试题。不过，要想去国外的大公司，比如Google、Facebook之类的，还是要研究得透彻一些才行。
另外，除应付面试之外，还有很重要的一点，甚至是更重要的一点，就是本书可以帮我们打开思路，因为很多算法题的解法是需要逆向思维的，需要跳出原有的固定思维模式，当思维模式被打开之后，你会发现原有的事物现在看起来会有不同的看法，因为角度变了。不过这只能自己体会。
后来才知道，程云举办算法交流是为写书做准备。用他的话说：“会做题不算什么，比我“刷”题多的人我也能找出一大堆，但能给人讲明白就不容易了。”于是我后来又变成了程云在写这本书期间的试读者。
在此书还未上市之前，就能听到作者面对面地逐一讲解每一道题，真是非常难得且宝贵的经历。
如果你和我一样，对数据结构有个大概的了解，很想快速掌握算法题的解法技巧，那么这本书一定适合你！
祝每一位勤奋努力的程序员都能拿到自己满意的职位！周宝鑫一个程序员
自序
我能出书挺意外的。
在6年前的某一天，虽然我早就知道想进入那些大公司要靠“刷”代码面试题来练习编写代码的能力。可是这一天却不止如此，我突然有了心情去看代码面试题长什么样子，于是收集了代码面试的题目，越深入，我越有一种恐慌的感觉，因为感觉自己什么都不太在行，对一个归并排序（Merge sort）写出完整的代码都感觉挺费劲的，面对这个冯·诺伊曼发明的排序算法，我真有底气说自己是计算机专业的学生吗？这种打击并没有持续太久，因为爱耍小聪明的人总会特别自信。我决定开始认真面对“刷”题这件事，但那时我根本不知道我即将面对什么，更不要谈有写书的念头。
我把课余时间利用起来，心想：不就是“刷”题吗？别人能写出来，咱也能写出来。起初的心态是我不服，我就想告诉自己能行。过程虐心是肯定的，经常半夜因为看到一个复杂度特别低的算法自己真的不能理解而沮丧地睡不着觉。当时觉得找不到什么资料能彻底让我明白，书上讲得太粗浅，网上的太散乱，代码写得看不懂。起初我“刷”题的时候无数次地想放弃，因为觉得这些都是什么玩意儿！我为什么放着好好的日子不过，去找这种罪受？可是我又不甘心，虽然我不懂很多解法，但是它们真的很有意思。
我将能买到的所有相关书籍上的所有题目全都研究了一遍，不管是中文的还是英文的，我都硬着头皮“啃”。写完每道题后，我都和书上的方法进行反复对比。“啃”完了五六本书之后，距离我刚开始“刷”题已经过去16个月了。写书？别逗了，才刚看完。“年轻人总会找借口说这个东西不是我感兴趣的，所以我做不好是应该的。但他们没有注意的是，你面对的事情中感兴趣的事情总是少数，这就使得大多数时候你做事情的态度总是很懈怠、很消极，这使你变成了一个懈怠的人。当你真正面对自己感兴趣的东西时，你发现你已经攥不紧拳头了。”时常想起本科时的毕业设计指导老师——高鹏义老师说的这句话。说得对！对一个东西，如果你没有透彻研究过，不要轻易说它不精彩。这不是博爱，而是对自己认真。“刷”题代码达到4万行的时候，我基本上成了国内外所有热门“刷”题网站的日常用户，此时我确认了一件事情，今天的代码面试指导真的处在一个很初级的阶段，这种不健全是全方面的。
例如：
·经常看到一篇文章前后的语境是割裂的，作者经常根据之前的一个优良解法提出更好的优化方式，但整篇文章都不提之前的解法是什么。这就导致初学者根本无法看懂；
·几乎所有的书籍都忽略例子带来的引导作用，甚至还有不少书籍在阐述一个解法的时候只写伪代码，这就使得读者在看懂意思和自己真正能写出代码之间其实还有很多的路要走；
·代码面试题目的特点是“多”、“杂”、“难”，从着手开始学习到最终达到自己想要的效果之间，自己对自己的评估根本无从谈起。“慢慢练吧，学海无涯”成为主要的心态，这就难免会产生怀疑的情绪；
·看见一道新的面试题时还是会无从下手，因为之前的学习无法做到举一反三，对自己做过的题目缺乏总结和归纳。
难道“刷”题真的只适合聪明人玩？我不这么看，既然大多数内容处在有待商榷的地步，那我就去学习原论文吧。
当时一个人在国外，记得在初冬的一个下午，“刷”题已经两年之久，快吃晚饭的时候，我突然想起自己忘了吃午饭，就冲出家门去觅食。站在7-11门前的广场上，我拿着1.5美元的热狗和75美分的咖啡，微温的阳光撒在眼睛里，远远地望着即将消失的一天。我停下来，把咖啡放在斑驳的石头台子上，手里的热狗挺好看，香肠和洋葱都挺新鲜，清冷的空气吹过来，却让我的心绪更乱。旧金山的天空五彩斑斓，让漂泊者头晕目眩。哭得跟个鬼似的我除了想家，哪里敢想自己会出书呢？
当我意识到在网上很难搜到新鲜的题目时，我已经换了两家公司，反复实现了600多道题目，写了差不多10万行代码。原来只是为了找份工作而“刷”题这一初心早就忘了，变成了兴趣并坚持了这么久，我自己也感到意外。更奇怪的是，我已经完全乐在其中，同时交流欲望越来越强，时常和同事们展开这方面的讨论。发现很多书上的解法不是最优，很多题目其实和同事们讨论的做法更好，发现高手特别多，但好像都懒得动笔。
有一天，我看到自己写的题目，想到自己那些抓心挠肝的日子，突然觉得要不出书吧？我已经离不开这种感觉了，如果这不是真爱，那什么才是呢？
这不是一个励志的故事，是一个爱“刷”题的人决定把很多最优解讲出来，就这么简单。左程云2015年7月20日第1章栈和队列设计一个有getMin功能的栈【题目】
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。【要求】
1．pop、push、getMin操作的时间复杂度都是O(1)。
2．设计的栈类型可以使用现成的栈结构。【难度】
士★☆☆☆【解答】
在设计上我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用于保存每一步的最小值，这个栈记为stackMin。具体的实现方式有两种。
第一种设计方案如下。·压入数据规则
假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空：
·如果为空，则newNum也压入stackMin。
·如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：
·如果newNum更小或两者相等，则newNum也压入stackMin；
·如果stackMin中栈顶元素小，则stackMin不压入任何内容。
举例：依次压入3、4、5、1、2、1的过程中，stockData和stackMin的变化如图1-1所示。图1-1·弹出数据规则
先在stackData中弹出栈顶元素，记为value。然后比较当前stackMin的栈顶元素和value哪一个更小。
通过上文提到的压入规则可知，stackMin中存在的元素是从栈底到栈顶逐渐变小的，stackMin栈顶的元素既是stackMin栈的最小值，也是当前stackData栈的最小值。所以不会出现value比stackMin的栈顶元素更小的情况，value只可能大于或等于stackMin的栈顶元素。
当value等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value大于stackMin的栈顶元素时，stackMin不弹出栈顶元素；返回value。
很明显可以看出，压入与弹出规则是对应的。·查询当前栈中的最小值操作
由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值，所以，stackMin的栈顶元素始终是当前stackData中的最小值。
方案一的代码实现如MyStack1类所示：
第二种设计方案如下。·压入数据规则
假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。
如果为空，则newNum也压入stackMin；如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：
如果newNum更小或两者相等，则newNum也压入stackMin；如果stackMin中栈顶元素小，则把stackMin的栈顶元素重复压入stackMin，即在栈顶元素上再压入一个栈顶元素。
举例：依次压入3、4、5、1、2、1的过程中，stockData和stackMin的变化如图1-2所示。图1-2·弹出数据规则
在stackData中弹出数据，弹出的数据记为value；弹出stackMin中的栈顶；返回value。很明显可以看出，压入与弹出规则是对应的。·查询当前栈中的最小值操作
由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值，所以stackMin的栈顶元素始终是当前stackData中的最小值。
方案二的代码实现如MyStack2类所示：【点评】
方案一和方案二其实都是用stackMin栈保存着stackData每一步的最小值。共同点是所有操作的时间复杂度都为O(1)、空间复杂度都为O(n)。区别是：方案一中stackMin压入时稍省空间，但是弹出操作稍费时间；方案二中stackMin压入时稍费空间，但是弹出操作稍省时间。由两个栈组成的队列【题目】
编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）。【难度】
尉★★☆☆【解答】
栈的特点是先进后出，而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。
具体实现上是一个栈作为压入栈，在压入数据时只往这个栈中压入，记为stackPush；另一个栈只作为弹出栈，在弹出数据时只从这个栈弹出，记为stackPop。
因为数据压入栈的时候，顺序是先进后出的。那么只要把stackPush的数据再压入stackPop中，顺序就变回来了。例如，将1～5依次压入stackPush，那么从stackPush的栈顶到栈底为5～1，此时依次再将5～1倒入stackPop，那么从stackPop的栈顶到栈底就变成了1～5。再从stackPop弹出时，顺序就像队列一样，如图1-3所示。图1-3
听起来虽然简单，实际上必须做到以下两点。
1．如果stackPush要往stackPop中压入数据，那么必须一次性把stackPush中的数据全部压入。
2．如果stackPop不为空，stackPush绝对不能向stackPop中压入数据。
违反了以上两点都会发生错误。
违反1的情况举例：1～5依次压入stackPush，stackPush的栈顶到栈底为5～1，从stackPush压入stackPop时，只将5和4压入了stackPop，stackPush还剩下1、2、3没有压入。此时如果用户想进行弹出操作，那么4将最先弹出，与预想的队列顺序就不一致。
违反2的情况举例：1～5依次压入stackPush，stackPush将所有的数据压入了stackPop，此时从stackPop的栈顶到栈底就变成了1～5。此时又有6～10依次压入stackPush，stackPop不为空，stackPush不能向其中压入数据。如果违反2压入了stackPop，从stackPop的栈顶到栈底就变成了6～10、1～5。那么此时如果用户想进行弹出操作，6将最先弹出，与预想的队列顺序就不一致。
上面介绍了压入数据的注意事项。那么这个压入数据的操作在何时发生呢？
这个选择的时机可以有很多，调用add、poll和peek三种方法中的任何一种时发生“压”入数据的行为都是可以的。只要满足如上提到的两点，就不会出错。
本书的实现是在调用poll和peek方法时进行压入数据的过程。
具体实现请参看如下的TwoStacksQueue类：如何仅用递归函数和栈操作逆序一个栈【题目】
一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底为1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。【难度】
尉★★☆☆【解答】
本题考查栈的操作和递归函数的设计，我们需要设计出两个递归函数。
递归函数一：将栈stack的栈底元素返回并移除。
具体过程就是如下代码中的getAndRemoveLastElement方法。
如果从stack的栈顶到栈底依次为3、2、1，这个函数的具体过程如图1-4所示。
递归函数二：逆序一个栈，就是题目要求实现的方法，具体过程就是如下代码中的reverse方法。该方法使用了上面提到的getAndRemoveLastElement方法。图1-4
如果从stack的栈顶到栈底依次为3、2、1，reverse函数的具体过程如图1-5所示。图1-5
getAndRemoveLastElement方法在图中简单表示为get方法，表示移除并返回当前栈底元素。猫狗队列【题目】
宠物、狗和猫的类如下：
实现一种狗猫队列的结构，要求如下：
·用户可以调用add方法将cat类或dog类的实例放入队列中；
·用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
·用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；
·用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；
·用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例；
·用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例；
·用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。【难度】
士★☆☆☆【解答】
本题考查实现特殊数据结构的能力以及针对特殊功能的算法设计能力。
本题为开放类型的面试题，希望读者能有自己的实现，在这里列出几种常见的设计错误：
·cat队列只放cat实例，dog队列只放dog实例，再用一个总队列放所有的实例。错误原因：cat、dog以及总队列的更新问题。
·用哈希表，key表示一个cat实例或dog实例，value表示这个实例进队列的次序。错误原因：不能支持一个实例多次进队列的功能需求，因为哈希表的key只能对应一个value值。
·将用户原有的cat或dog类改写，加一个计数项来表示某一个实例进队列的时间。错误原因：不能擅自改变用户的类结构。
本题实现将不同的实例盖上时间戳的方法，但是又不能改变用户本身的类，所以定义一个新的类，具体实现请参看如下的PetEnterQueue类。
PetEnterQueue类在构造时，pet是用户原有的实例，count就是这个实例的时间戳。
我们实现的队列其实是PetEnterQueue类的实例。大体说来，首先有一个不断累加的数据项，用来表示实例进队列的时间；同时有两个队列，一个是只放dog类实例的队列dogQ，另一个是只放cat类实例的队列catQ。
在加入实例时，如果实例是dog，就盖上时间戳，生成对应的PetEnterQueue类的实例，然后放入dogQ；如果实例是cat，就盖上时间戳，生成对应的PetEnterQueue类的实例，然后放入catQ。具体过程请参看如下DogCatQueue类的add方法。
只想弹出dog类的实例时，从dogQ里不断弹出即可，具体过程请参看如下DogCatQueue类的pollDog方法。
只想弹出cat类的实例时，从catQ里不断弹出即可，具体过程请参看如下DogCatQueue类的pollCat方法。
想按实际顺序弹出实例时，因为dogQ的队列头表示所有dog实例中最早进队列的实例，同时catQ的队列头表示所有的cat实例中最早进队列的实例。则比较这两个队列头的时间戳，谁更早，就弹出谁。具体过程请参看如下DogCatQueue类的pollAll方法。
DogCatQueue类的整体代码如下：用一个栈实现另一个栈的排序【题目】
一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？【难度】
士★☆☆☆【解答】
将要排序的栈记为stack，申请的辅助栈记为help。在stack上执行pop操作，弹出的元素记为cur。
·如果cur小于或等于help的栈顶元素，则将cur直接压入help；
·如果cur大于help的栈顶元素，则将help的元素逐一弹出，逐一压入stack，直到cur小于或等于help的栈顶元素，再将cur压入help。
一直执行以上操作，直到stack中的全部元素都压入到help。最后将help中的所有元素逐一压入stack，即完成排序。用栈来求解汉诺塔问题【题目】
汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有N层的时候，打印最优移动过程和最优移动总步数。
例如，当塔数为两层时，最上层的塔记为1，最下层的塔记为2，则打印：
注意：关于汉诺塔游戏的更多讨论，将在本书递归与动态规划的章节中继续。【要求】
用以下两种方法解决。
·方法一：递归的方法；
·方法二：非递归的方法，用栈来模拟汉诺塔的三个塔。【难度】
校★★★☆【解答】
方法一：递归的方法。
首先，如果只剩最上层的塔需要移动，则有如下处理：
1．如果希望从“左”移到“中”，打印“Move 1 from left to mid”。
2．如果希望从“中”移到“左”，打印“Move 1 from mid to left”。
3．如果希望从“中”移到“右”，打印“Move 1 from mid to right”。
4．如果希望从“右”移到“中”，打印“Move 1 from right to mid”。
5．如果希望从“左”移到“右”，打印“Move 1 from left to mid”和“Move 1 from mid to right”。
6．如果希望从“右”移到“左”，打印“Move 1 from right to mid”和“Move 1 from mid to left”。
以上过程就是递归的终止条件，也就是只剩上层塔时的打印过程。
接下来，我们分析剩下多层塔的情况。
如果剩下N层塔，从最上到最下依次为1～N，则有如下判断：
1．如果剩下的N层塔都在“左”，希望全部移到“中”，则有三个步骤。
1）将1～N-1层塔先全部从“左”移到“右”，明显交给递归过程。
2）将第N层塔从“左”移到“中”。
3）再将1～N-1层塔全部从“右”移到“中”，明显交给递归过程。
2．如果把剩下的N层塔从“中”移到“左”，从“中”移到“右”，从“右”移到“中”，过程与情况1同理，一样是分解为三步，在此不再详述。
3．如果剩下的N层塔都在“左”，希望全部移到“右”，则有五个步骤。
1）将1～N-1层塔先全部从“左”移到“右”，明显交给递归过程。
2）将第N层塔从“左”移到“中”。
3）将1～N-1层塔全部从“右”移到“左”，明显交给递归过程。
4）将第N层塔从“中”移到“右”。
5）最后将1～N-1层塔全部从“左”移到“右”，明显交给递归过程。
4．如果剩下的N层塔都在“右”，希望全部移到“左”，过程与情况3同理，一样是分解为五步，在此不再详述。
以上递归过程经过逻辑化简之后的代码请参看如下代码中的hanoiProblem1方法。
方法二：非递归的方法——用栈来模拟整个过程。
修改后的汉诺塔问题不能让任何塔从“左”直接移动到“右”，也不能从“右”直接移动到“左”，而是要经过中间。也就是说，实际动作只有4个：“左”到“中”、“中”到“左”、“中”到“右”、“右”到“中”。
现在我们把左、中、右三个地点抽象成栈，依次记为LS、MS和RS。最初所有的塔都在LS上。那么如上4个动作就可以看作是：某一个栈（from）把栈顶元素弹出，然后压入到另一个栈里（to），作为这一个栈（to）的栈顶。
例如，如果是7层塔，在最初时所有的塔都在LS上，LS从栈顶到栈底就依次是1～7，如果现在发生了“左”到“中”的动作，这个动作对应的操作是LS栈将栈顶元素1弹出，然后1压入到MS栈中，成为MS的栈顶。其他的操作同理。
一个动作能发生的先决条件是不违反小压大的原则。
from栈弹出的元素num如果想压入到to栈中，那么num的值必须小于当前to栈的栈顶。
还有一个原则不是很明显，但也是非常重要的，叫相邻不可逆原则，解释如下：
1．我们把四个动作依次定义为：L-＞M、M-＞L、M-＞R和R-＞M。
2．很明显，L-＞M和M-＞L过程互为逆过程，M-＞R和R-＞M互为逆过程。
3．在修改后的汉诺塔游戏中，如果想走出最少步数，那么任何两个相邻的动作都不是互为逆过程的。举个例子：如果上一步的动作是L-＞M，那么这一步绝不可能是M-＞L，直观地解释为：你上一步把一个栈顶数从“左”移动到“中”，这一步为什么又要移回去呢？这必然不是取得最小步数的走法。同理，M-＞R动作和R-＞M动作也不可能相邻发生。
有了小压大和相邻不可逆原则后，可以推导出两个十分有用的结论——非递归的方法核心结论：
1．游戏的第一个动作一定是L-＞M，这是显而易见的。
2．在走出最少步数过程中的任何时刻，四个动作中只有一个动作不违反小压大和相邻不可逆原则，另外三个动作一定都会违反。
对于结论2，现在进行简单的证明。
因为游戏的第一个动作已经确定是L-＞M，则以后的每一步都会有前一步的动作。
假设前一步的动作是L-＞M：
1．根据小压大原则，L-＞M的动作不会重复发生。
2．根据相邻不可逆原则，M-＞L的动作也不该发生。
3 ．根据小压大原则，M-＞R和R-＞M只会有一个达标。
假设前一步的动作是M-＞L：
1．根据小压大原则，M-＞L的动作不会重复发生。
2．根据相邻不可逆原则，L-＞M的动作也不该发生。
3．根据小压大原则，M-＞R和R-＞M只会有一个达标。
假设前一步的动作是M-＞R：
1．根据小压大原则，M-＞R的动作不会重复发生。
2．根据相邻不可逆原则，R-＞M的动作也不该发生。
3．根据小压大原则，L-＞M和M-＞L只会有一个达标。
假设前一步的动作是R-＞M：
1．根据小压大原则，R-＞M的动作不会重复发生。
2．根据相邻不可逆原则，M-＞R的动作也不该发生。
3．根据小压大原则，L-＞M和M-＞L只会有一个达标。
综上所述，每一步只会有一个动作达标。那么只要每走一步都根据这两个原则考查所有的动作就可以，哪个动作达标就走哪个动作，反正每次都只有一个动作满足要求，按顺序走下来即可。
非递归的具体过程请参看如下代码中的hanoiProblem2方法。生成窗口最大值数组【题目】
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：
如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
请实现一个函数。
·输入：整型数组arr，窗口大小为w。
·输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。以本题为例，结果应该返回{5,5,5,4,6,7}。【难度】
尉★★☆☆【解答】
如果数组长度为N，窗口大小为w，如果做出时间复杂度O(N×w)的解法是不能让面试官满意的，本题要求面试者想出时间复杂度O(N)的实现。
本题的关键在于利用双端队列来实现窗口最大值的更新。首先生成双端队列qmax，qmax中存放数组arr中的下标。
假设遍历到arr[i]，qmax的放入规则为：
1．如果qmax为空，直接把下标i放进qmax，放入过程结束。
2．如果qmax不为空，取出当前qmax队尾存放的下标，假设为j。
1）如果arr[j]＞arr[i]，直接把下标i放进qmax的队尾，放入过程结束。
2）如果arr[j]＜=arr[i]，把j从qmax中弹出，继续qmax的放入规则。
假设遍历到arr[i]，qmax的弹出规则为：
如果qmax队头的下标等于i-w，说明当前qmax队头的下标已过期，弹出当前对头的下标即可。
根据如上的放入和弹出规则，qmax便成了一个维护窗口为w的子数组的最大值更新的结构。下面举例说明题目给出的例子。
1．开始时qmax为空，qmax={}
2．遍历到arr[0]==4，将下标0放入qmax，qmax={0}。
3．遍历到arr[1]==3，当前qmax的队尾下标为0，又有arr[0]＞arr[1]，所以将下标1放入qmax的尾部，qmax={0,1}。
4．遍历到arr[2]==5，当前qmax的队尾下标为1，又有arr[1]＜=arr[2]，所以将下标1从qmax的尾部弹出，qmax变为{0}。当前qmax的队尾下标为0，又有arr[0]＜=arr[2]，所以将下标0从qmax尾部弹出，qmax变为{}。将下标2放入qmax，qmax={2}。此时已经遍历到下标2的位置，窗口arr[0..2]出现，当前qmax队头的下标为2，所以窗口arr[0..2]的最大值为arr[2]（即5）。
5．遍历到arr[3]==4，当前qmax的队尾下标为2，又有arr[2]＞arr[3]，所以将下标3放入qmax尾部，qmax={2,3}。窗口arr[1..3]出现，当前qmax队头的下标为2，这个下标还没有过期，所以窗口arr[1..3]的最大值为arr[2]（即5）。
6．遍历到arr[4]==3，当前qmax的队尾下标为3，又有arr[3]＞arr[4]，所以将下标4放入qmax尾部，qmax={2,3,4}。窗口arr[2..4]出现，当前qmax队头的下标为2，这个下标还没有过期，所以窗口arr[2..4]的最大值为arr[2]（即5）。
7．遍历到arr[5]==3，当前qmax的队尾下标为4，又有arr[4]＜=arr[5]，所以将下标4从qmax的尾部弹出，qmax变为{2,3}。当前qmax的队尾下标为3，又有arr[3]＞arr[5]，所以将下标5放入qmax尾部，qmax={2,3,5}。窗口arr[3..5]出现，当前qmax队头的下标为2，这个下标已经过期，所以从qmax的头部弹出，qmax变为{3,5}。当前qmax队头的下标为3，这个下标没有过期，所以窗口arr[3..5]的最大值为arr[3]（即4）。
8．遍历到arr[6]==6，当前qmax的队尾下标为5，又有arr[5]＜=arr[6]，所以将下标5从qmax的尾部弹出，qmax变为{3}。当前qmax的队尾下标为3，又有arr[3]＜=arr[6]，所以将下标3从qmax的尾部弹出，qmax变为{}。将下标6放入qmax，qmax={6}。窗口arr[4..6]出现，当前qmax队头的下标为6，这个下标没有过期，所以窗口arr[4..6]的最大值为arr[6]（即6）。
9．遍历到arr[7]==7，当前qmax的队尾下标为6，又有arr[6]＜=arr[7]，所以将下标6从qmax的尾部弹出，qmax变为{}。将下标7放入qmax，qmax={7}。窗口arr[5..7]出现，当前qmax队头的下标为7，这个下标没有过期，所以窗口arr[5..7]的最大值为arr[7]（即7）。
10．依次出现的窗口最大值为[5,5,5,4,6,7]，在遍历过程中收集起来，最后返回即可。
上述过程中，每个下标值最多进qmax一次，出qmax一次。所以遍历的过程中进出双端队列的操作是时间复杂度为O(N)，整体的时间复杂度也为O(N)。具体过程参看如下代码中的getMaxWindow方法。构造数组的MaxTree【题目】
定义二叉树节点如下：
一个数组的MaxTree定义如下。
·数组必须没有重复元素。
·MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点。
·包括MaxTree树在内且在其中的每一棵子树上，值最大的节点都是树的头。
给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，则时间复杂度为O(N)、额外空间复杂度为O(N)。【难度】
校★★★☆【解答】
下面举例说明如何在满足时间和空间复杂度的要求下生成MaxTree。
以下列原则来建立这棵树：
·每一个数的父节点是它左边第一个比它大的数和它右边第一个比它大的数中，较小的那个。
·如果一个数左边没有比它大的数，右边也没有。也就是说，这个数是整个数组的最大值，那么这个数是MaxTree的头节点。
那么3, 4, 5, 1, 2的MaxTree如下：
为什么通过这个方法能够正确地生成MaxTree呢？我们需要给出证明，证明分为如下两步。
1．通过这个方法，所有的数能生成一棵树，这棵树可能不是二叉树，但肯定是一棵树，而不是多棵树（森林）。
我们知道，在数组中的所有数都不同，而一个较小的数肯定会以一个比自己大的数作为父节点，那么最终所有的数向上找都会找到数组中的最大值，所以它们会有一个共同的头。证明完毕。
2．通过这个方法，所有的数最多都只有两个孩子。也就是说，这棵树可以用二叉树表示，而不需要多叉树。
要想证明这个问题，只需证明任何一个数在单独一侧，孩子数量都不可能超过1个即可。
假设a这个数在单独一侧有2个孩子，不妨设在右侧。假设这两个孩子一个是k1，另一个是k2，即
因为a是k1和k2的父，所以a＞k1，a＞k2。根据题意，k1和k2不相等，所以k1和k2可以分出大小，先假设k1是较小的，k2是较大的：
那么k1可能会以k2为父节点，而绝对不会以a为父节点，因为根据我们的方法，每一个数的父节点是它左边第一个比它大的数和它右边第一个比它大的数中较小的那个，又有a＞k2。
再假设k2是较小的，k1是较大的：
那么k2可能会以k1为父节点，也绝对不会以a为父节点，因为根据我们的方法，k1才可能是k2左边第一个遇到的比k2大的数，而绝对不会轮到a。
总之，k1和k2肯定有一个不是a的孩子。
所以，任何一个数的单独一侧，其孩子数量都不可能超过1个，最多只会有1个。进而我们知道，任何一个数最多会有2个孩子，而
试读结束[说明：试读内容隐藏了图片]