如果没有空间复杂度为O(1)的要求，这个题目非常简单，简单的做一下切片处理就可以了

我们只能使用一个O(1)的空间来临时存储数据，简单说，一次只能存储一个数字，但要向右移动K个位置。如果我们能找到一种算法，这个算法执行一次，只将数组向右移动1位，移动k个位置只需要执行这个算法K次就可以了。

考虑移动1位就简单了，用一个临时变量tmp将lst[-1]保存下来，然后从后向前，逐个向后移动，最后，将lst[0]赋值为tmp

写一个for循环，遍历列表lst，逐个打开文件，逐行读取文件里的信息，将读取的每一行数据写入到all.txt文件中，就是这么简单

请写程序拆分这个文件，文件里的内容，以1开头的，就写入到1.txt文件中，以2开头的内容，写入到2.txt文件中，依次类推

打开文件，逐行读取文件内容，解析出一行内容的第一个字符，用第一个字符串拼接处要写入的文件名字，然后以a+方式打开文件，将这一行文件写入到文件中

8 地狱难度算法练习题
8.1 删除有序序列中的重复项
已知一个有序序列,请原地删除序列中重复出现的元素,返回删除重复元素后的序列长度。

只能使用O(1)额外空间，必须原地删除
需要返回删除重复元素后的长度，如果长度为N，那么序列前N个元素没有重复元素
设置一个哨兵index，初始值赋为0。用一个for循环从索引1开始遍历lst，i做迭代变量， 如果lst[i]!=lst[index]，就说明lst[i]是一个比lst[index]大的元素，它应该被放置在index+1的位置上

将lst[i] 放置在index+1位置上以后，要向右移动哨兵的位置，执行index += 1，这样，即便lst[i]这个值在后面重复出现了，可此时lst[index]=lst[i]，所以重复出现的值会被忽略掉，直到遇到一个与lst[index]不相等的元素，再次移动哨兵

序列中的元素可以被多次选用,不能出现重复的组合, 序列中的元素和目标数都是正整数。

编程不是拿着画笔随心所欲的在画板上涂抹，也不存在固定的方法帮你完成具体的问题，做练习题的目的是通过这些练习题锻炼你的思维，当你建立起编程的思维以后，你也就不在乎什么具体方法和套路，面对具体问题时，你将有能力进行分析。

当问题复杂无从下手时，你可以从问题的边界处入手，题目没有对组合里的元素个数做限制，那么你就先考虑组合里只有一个元素的情况，题目就变成了从序列中找到1个元素，这个元素的值等于目标元素，这样，问题不就变得简单了么

接下来考虑两个元素的情况，从序列中找到两个数，这两个数的和等于目标数target，先随便从序列中选定一个数，假设这个数是i, 那么接下来要做的就是从序列中找到1个元素且这个元素等于target - i

接下来思考三个元素的情况，从序列中找到三个数，这三个数的和等于目标数target，你可以先随便从序列中选定一个数，假设这个数是i，那么接下来要做的就是从序列中找到两个元素且这两个元素的和等于target - i

新的问题，总是转化为老的问题，而最老的那个问题，从序列中找到一个元素且这个元素的值等于目标值是非常容易解决的。

当分析问题遇到阻碍，我最喜欢从问题的边界处入手，因为边界的地方正是条件达到极值的时候，这时候，很容易就找出破绽。

T的首字母是r， 这个r恰好也是S的首字母，如果让S = "abbbitr" ，让r成为S的末尾字符，问题似乎一下子变得明朗起来，此时，S的任意子序列都不可能是“rabbit“， 因为S中r字符后的后面没有内容了，根本找不到”abbit“，顺着这个思路想下去，想从S的子序列中找到T，就必须满足S中，r的后面可以找到a，a的后面可以找到b，b的后面可以再找到一个b，b的后面可以找打一个i,i的后面可以找到t。

但这样找还是挺麻烦的，为何不把T中每个字符出现在S中的位置记录下来呢？r出现在0的位置上，b出现在2, 3, 4的位置上，用一个字典来保存T中字符在S中出现位置的信息：

,有三个位置可以挑选，需要注意的是，如果T[i]这个字符挑选了位置index，那么T[i+1]这个字符在挑选位置时就不能选小于等于index。假如S=”brabbbit“, 那么在选b的位置的时候，就不能要0这个位置，因为T中a在b的前面，a已经选了2这个位置，b选到0毫无意义，这样不能构成子序列。

分析到这里，就演变成了一个寻找排列组合的问题。

逆波兰表达式的计算，其实是栈这种数据结构的经典应用，将逆波兰表达式中的元素逐一放入一个栈中，当遇到运算符时，则从栈顶连续弹出两个元素进行计算，然后把计算结果放入到栈中，最后，栈里只有保存一个元素，这个元素就是整个表达式的计算结果。

因此这道题目，你需要实现一个简单的栈，好在有列表这种神器，栈的实现非常容易。

有一个比较坑的地方是python的除法，python中，采用的是向下取整的办法，比如

其他语言中，5/-3会向上取整，就会得到-1， 这个是符合我们日常判断的，但python里却偏偏向下取整得到了-2，为了使结果符合人们的常识，需要用到operator 模块的truediv 方法。

以列表中的第一个单词作为基线，其余的单词逐个字符与第一个单词的字符进行比较，比如以flower做为基线，flower第一个字符是f，那么其余的单词的第一个字符也是f，就将这个f记录下来，逐一比较，直到某个位置上的字符出现不一致的情况。

在比较过程中，要注意单词的长度，如果某个单词已经比较到末尾，那么就可以停止了，因为这个单词的长度就是理论上可能的最大公共前缀

我们先随便定义一个区间，比如说[9, 18], 怎么判断这k个列表里每个列表都有元素包含其中呢？这需要遍历每一个列表，列表里的元素只要有一个在9到18之间就可以了。可是这样的遍历好麻烦，因为列表有多个，何不考虑把这k个列表合并成一个呢，这样就只有一个列表存在，寻找区间就不需要对每个列表都检查了。

但是合并区间带来一个新的问题，合并以后，对于一个数，你不知道这个数来自于哪个列表，因此，合并的过程，需要记录每一个数都在哪个列表中出现过，可以使用一个字典（index_dict），用数值做key,value设置为set，存入小列表在大列表中的索引。

经过上面两步分析，可以得到一个合并后的列表，且知道列表中的每个数在哪个小列表中出现过。

接下来就是寻找区间，还是老办法，考虑极值或边界情况，假设合并列表的第一个元素（item）就是最小区间开始的位置，那么只要解决结束位置就好了，要记住，每个元素曾经在哪个小列表中出现过是有记录的，此时可以查看第一个元素在小列表中出现的情况，如果len(index_dict[item]) 和 len(big_lst)相等，就可以证明，item在每个小列表中都出现过。这样最小区间就是[item, item]。

成立，就找到了最小区间的结束位置。

前面的分析，是建立在合并列表的第一个元素是最小区间的起始元素的基础上，依靠这个边界条件，理清的思路，接下来要推广到合并列表的每一个元素，遍历合并列表，并假设当前遍历到的元素就是最小区间的起始元素，然后寻找最小区间结束的元素。

返回森林中兔子的最少数量

这类编程题，考察的不是编码能力，而是思考能力。首先要明确一点，这些兔子不会撒谎，否则，就没有答案了。

当思考问题时感到无从下手，就考虑边界或极值情况，我们假设森林中所有兔子都是相同的颜色，而且都会告诉你有多少其他的兔子和自己有相同的颜色，那么这会是怎样的局面呢？

假设森林中有3只兔子，那么答案一定是[2, 2, 2]，如果森林中有5只兔子，那么答案一定是[4, 4, 4, 4, 4]。当你限制了那些变化的条件，问题就变得清晰明了了，有N只兔子，就有N个答案，且答案一定是N-1，兔子是不会说谎的。

现在，来分析题目给的例子，[1, 1, 2]，有兔子回答2，就说明有3只兔子是一样的颜色，只有一只兔子回答了，其他两只没有回答，有两只兔子回答了1，他们两个可能是相同的颜色，也可能是不同的颜色，题目要求算最少的数量，那就认为他们是相同的颜色吧，这样就是5只兔子。

如果答案是 [1, 1, 2, 2, 2, 2]呢，森林中最少有8只兔子，2个回答1的兔子是相同颜色，3个回答2的兔子是相同颜色，还有一只兔子回答2，这就说明还有两个兔子和这只兔子颜色相同，但是他们没有回答。

分析到这里，不难得出一个简单的结论，如果一只兔子回答N，那么森林中必然有N+1只兔子颜色相同，剩余的N只兔子可能来回答了，也可能没有来回答，假设都来回答，那就有N+1个答案为N，可是如果出现了N+2个兔子回答N，就说明又多出来N+1只兔子，多出来的这组兔子只有一只来回答了。

你需要做的是统计每个答案的个数，比如 [1, 1, 2, 2, 2, 2]，回答情况如下

动态规划的算法，难与易只在一念之间，掌握了动态规划的精髓，代码轻易的就能写出，反之，则陷入到茫然之中。

动态规划的题目，其实，都可以用暴力破解，但真正的解法都非常的巧妙，说是巧妙，并不是投机取巧，而是掌握了动态规划的实质。

既然是动态，那么到底是什么在动呢？假设数组为k，令max_sum表示最大子数组之和，已知从k[i]到[j]的的和为pre_sum，暂且让max_sum = pre_sum，那么现在，我们要考虑是否应该让k[j+1]也加到这个子数组之中，多一个数，可能让max_sum更大哦。

k[j+1]之后，的确变小了，但是max_sum还是之前的那个最大值，之所以要加k[j+1]，因为k[j+2]有可能是一个很大的正数啊，所以要继续探索可能的最大子数组之和。那么假如k[j+2]也是负数呢，而且是很大的负数，以至于加上k[j+2]之后，pre_sum<0, 如果这样的事情发生，就按下面的方法操作

k[j+1]，表示重新开始寻找和最大的子数组，如果不重新开始，带着pre_sum这个负数，难道对求和不是一个负面效果么。

谁在动呢，是pre_sum一直在动，我们规划的是一个子数组，期初，这个子数组里只有一个元素，就是数组的第一个元素k[0],随后就是考虑要不要把k[1]加进来，是否加进来，就按照上面的说的方法来进行。

既然是动态规划，就要找到那个变化的点，就这道题目而言，变化的点就是连续子数组之和小于0了，这个时候就必须从新开始寻找了，因为这个和已经是负数了，就如同一个包袱，就算后面的数都是正数，加上一个负数也终究比都是整数要小。

实现一个简单的计算器，能够计算简单字符串表达式，表达式可以包括小括号，运算符包含+ - * /, 表达式允许有空格,参与运算的数值都是正整数。

万事开头难，先不考虑如何计算，我们应该先对表达式进行处理，处理以后，只有数值和运算符，这样才能对他们进行具体的操作，比如"1 + 2" 处理后得到['1', '+', '2']， 运算符和数值都分离开了。

这样的解析并不复杂，只需要遍历字符串，解析出数值部分放入到列表中，遇到小括号或者运算符则直接放入列表中，代码如下：

后序表达式相比于中序表达式更容易计算，因此，这一小节，我要把中序表达式转换成后序表达式。

转换时要借助栈这个数据结构，变量postfix_lst 表示后序表达式，遍历中序表达式，根据当前值进行处理：

如果遇到数值，则放入到postfix_lst中
遇到 ），将栈顶元素弹出并放入到postfix_lst中，直到遇到（，最后弹出（
遇到运算符，把栈顶元素弹出并放入到postfix_lst中，直到栈顶操作符的运算优先级小于当前运算符，最后将当前运算符压入栈

一个元素为数值的列表，找到其最长上升子序列的长度。

假设列表lst长度为k，创建一个长度同样为k的列表dp,dp内所有元素初始化为1，dp[i]代表以lst[i]结尾的最长上升子序列长度，这其实是一个假设，对于单个元素来说，也是列表的子序列，而且是上升的。

对于lst[0]来说，它自己就是一个子序列，单个元素，也可以视为上升的，因此，dp[0] 等于1，真实的表示了以lst[0]结尾的最长上升子序列的长度，但对于lst[j], j >0 来说，dp[j]就目前而言，还不能准确表示以lst[j]结尾的最长上升子序列的长度，不过没关系，计算dp[1]时，我们可以借助dp[0]，计算dp[2]时，可以借助dp[0]，dp[1]，计算dp[j]时，可以借助dp[0]到dp[j-1]。

遍历数组，每个当前元素都和自己右侧的元素比较，如果当前元素大于右侧的元素，则当前这个元素的索引就是山脉数组的顶峰索引

上面的算法虽然很简单，但效率并不高，可以使用二分查找法获得更快的速度。二分查找法利用了数组的有序性，山脉数组虽然不是有序的，但是峰顶前和峰顶后却各自有序，前者是升序，后者是降序，那么同样可以利用二分查找法进行查找

为什么在取值时用的索引是middle - 1呢，其实原因很简单，我们要找第k大的数，k最小是1，你不能说取第0大的数，我们日常是从1开始计数的，而计算机是从0开始计数的，middle = k/2， 从k计算而来，因此在使用索引时要减 1 。

要让数组长度更小的为a

计算middle时，其实要考虑middle是否比a的长度小，不然取a[middle-1]时就出错了，计算middle和 middle_ex为的是从a， b 两个数组里各自找到第middle大和第middle_ex大的两个数，通过比较他们的大小，决定舍弃哪一部分

不断的舍弃，不断的修改k的值，最后，一定会出现k==1的情况，这时，返回min(a[0], b[0])

每行的元素从左到右是升序的
每列的元素从上到下是升序的

每行数据和每列数据都是升序的，但行与行之间并没有升序关系，第二行的数据并不是都比第一行大。因此，搜索数据时，必须从第一行开始进行搜索。

搜索某一行时，由于数据有序，因此可以轻松的找到最小值和最大值

如果最小值比target大，可以确定整个矩阵里都没有目标值
如果最大值比target小，说明这一行里肯定不存在目标值。
如果target>= min and target <= max，就在这一行里进行查找，关键之处在于，如果这一行里没有找到目标值，还要继续去下一行里查找么？答案是肯定的，比如你想找5，第一行里没有找到，但是第二行里却可以找得到，而且，你无法跳过第一行直接查找第二行，因为第一行里可能有5
前面的三点分析，已经让搜索算法非常高效了，接下来要考虑如何高效的在一行数据里查找目标值，由于每一行数据是有序的，因此可以使用二分查找法，二分查找法已经非常高效了，但是由于每一列从上到下也是升序的，因此，可以对二分查找法稍稍做一点改变，就可以让整个的查找速度更快。

如果二分查找法在找不到目标值时，返回第一个比目标值大的元素的索引，那么，这个索引就可以作为下一次查找时结束位置的边界，比如搜索9，对第一行使用二分查找法搜索时没有找到目标值，但是找到了第一个比9大的元素11，索引为3，由于每一列都是升序的，所以搜索第二行时，不需要搜索整行，只需要搜索0到2这个索引范围就可以了。通过对二分查找法小做修改，就使得之后的每一行搜索范围得以缩小，效率更高。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）

一种思路是从t中寻找长度和s相同的子序列，然后判断这些子序列中有没有和s相等的子序列。这虽然是一个可行的方案，但显然效率很差。

另一个思路是先对t进行分析，遍历t获得每一个字符的出现位置，最终将得到一个字符分布的信息，例如“ahbgdc”, 它的字符分布情况是

得到这些字符分布情况后，就可以根据每个字符的所在位置来判断字符串s是否是t的子序列，假设a出现的位置都大于b出现的位置，那么字符串s一定不是字符串t的子序列，每个字符可以出现在很多个位置上，我们只要找到一个位置满足s是t的子序列就可以了。

以"abc" 为例，先找到a出现的位置，不论有多少个，只取第一个，记为pre_index，因为a的位置越靠前，留给bc的空间就越大，那么接下来从出现的位置中寻找第一个比pre_index大的位置并赋值给pre_index，为什么要找第一个，因为b的位置越靠前，留给c的空间就越大，最后从c的位置找到第一个比pre_index大的位置

这个题目本质上就是最长公共子串算法，使用动态规划算法就可以轻松解决。

假设A[i] == B[j], 这时，我们不去考虑A[i+1]好B[j+1]的关系，而是考虑A[i-1]和B[j-1]的关系。动态规划，总是依据前面的结果来计算当前的结果。

那么要依据前面的什么结果呢？假设A[i]和B[j]是最长公共子串的结尾处，那么我们用DP[i+1][j+1]记录这个子串的长度。 现在，请考虑DP[i][j]表达的含义是什么呢？ 它表示以A[i-1]和B[j-1]结尾的公共子串的长度，且DP[i][j] + 1 = DP[i+1][j+1]。

为什么要用DP[i+1][j+1]来记录以A[i]和B[j]结尾的公共子串的长度呢？看起来，下角标不一致，感觉怪怪的。

之所以这样做，是因为动态规划总是用前面的结果来计算当前的结果。当我们计算DP[i+1][j+1]时，需要用到DP[i][j]，i和j都是从0开始的。当我们考虑A[0]和B[0]的关系时，我们想要计算的是DP[1][1]，这时，我们就可以利用DP[0][0],如果用DP[0][0]表示以A[0],B[0]结尾的公共子串的长度，那么我们就不得不利用DP[-1][-1]+1来计算DP[0][0]，但是DP[-1][-1]并不存在。

因此，DP这个二维矩阵的第一行和第一列都设置为0，如此，就可以完全使用DP[i][j] + 1 = DP[i+1][j+1] 这个公式来进行计算，如下图所示

第一个大于等于目标值的元素位置
题目要求找到K个最接近目标值的元素，我们先不考虑K个，而是考虑1个的情况，也就是最接近目标值的那个元素。

如果数组里有某个元素恰好和目标值相等，那么问题就转变成了二分查找法，在数组中查找目标值。如果数组里没有目标值呢，如何找到距离目标值最近的元素呢？

不妨先找到第一个大于等于目标值的元素，找到了这个元素，也就容易找到距离目标值最近的那个元素了，分析到这里，我们先要实现一个函数，该函数可以从数组中找到第一个大于等于目标值的元素位置，下面是这个函数的示例代码

距离目标值最近的元素位置
前面的find_eg_index函数返回了第一个大于等于target的元素的位置eg_index，在此基础上，很容易就算出来距离target最近的元素的位置，所要考虑的逻辑分支如下

这里要考虑边界情况，如果left_index 超出了数组的索引范围，该如何比较呢，一侧超出了索引范围，剩余的最近元素一定集中在另一侧，此时，可以直接从另一侧数组里直接取剩余数量的元素，但我认为这样程序就会写的很复杂，要判断两侧的索引是否超出范围，要写很多if语句。

不弱这样处理，如果索引超出了范围，就认为这个索引上的元素是无穷大，这样就不需要判断左右两个索引是否超出范围以及取另一侧的剩余最近元素了。

第一位有4个选择，第一位确定后，第二位有3个选择，同理，第三位有2个选择，最后一位只有一个选择。

当我们用程序实现时，想要的不是排列组合的数量，而是要输出这些组合的内容，就不仅仅是一个算出一个数值那么简单。但算法归根结底还是数学问题，因此，我们可以回忆借鉴数学课上所学的方法，来考虑程序的算法逻辑。

第一步，确定第一个位置的情况，你可以写一个循环，让每个元素都有一次机会放在第一个位置上

第二步，对于剩余的三个元素，问题转变成这3个元素有多少全排列情况，这就变成了递归

经过上面两步思考，我们大致有了这样的代码逻辑

递归必须有终止条件，而且这个终止条件非常容易找到，start 和 end相等时，就表明没有什么元素需要经过变换位置来组成新的排列组合了。

不过到目前位置，我们还没有把这些排列组合记录下来，于是，有了下面的改进

每一次递归调用时，我们将元素的顺序进行了调整，注意看 [3, 1, 4, 2] 这个结果，这是3放到第一个位置时的组合之一，此时列表最后一个元素是2，还记得全排列的思路么，让每一个元素都有机会放在第一个位置上，这个逻辑对应到代码

为了避免重复，我们需要将列表里的元素还原，每次递归调用结束后，将之前互换位置的元素再次互换位置，只需增加一行代码就可以

第三次和第四次做同样的操作，这么一分析，你就应该想到用递归函数来做了。

截取后的每一段，如果是以0开头，那么这一段只能是0，总不能出现10.21.01.23的ip地址吧，01是什么鬼
截取后的每一段，其值大小不能超过255

如果截取后剩余的部分长度超过剩余几段理论上的最大长度,那么这个截取就是不合理的，比如， 第一段只截取1，那么剩余部分 的长度是11，后面三段最长也就是9，所以这样截取是不合理的

如果截取后余下的部分长度是0，也是不合理的

如果截取后余下的部分长度比余下几段理论上的最小长度还小，也是不合理的，比如截取后余下部分长度是2，可是还有3段需要截取，这样就是不合理的

解释: 任意两个c交换位置，都可以让A=B,他们是亲密字符串

解释：A字符串内部不论怎样交换，都不可能与B相同
如果A==B成立，那么就必须满足，A中有某个字符出现了两次或以上，只有这样，才能满足交换两个字符后与B相等，这是示例1的情况

如果A!=B，满足亲密字符串的条件就是A与B有两处不相同，而且交换这两处不相同的字符后A==B成立，这是示例2 的情况

如果A B两个字符串的长度不相等，必然不是亲密字符串。

遍历两个字符串，统计相同索引字符不相同的次数，如果次数是0，那么就必须满足A字符串有某个字符出现了两次或以上，可以用一个集合来保存A中的字符，如过有某个字符出现了两次或以上，那么最终，集合的大小一定小于A字符串的长度。

如果不相同的次数是2，那么交错对比这两处字符，如果不相同次数既不是0也不是2，则一定不是亲密字符串

只包含1的正方形可以出现在矩阵的任意位置，所以，不要妄想通过什么巧妙的办法快速的找到这个正方形的位置，正确的做法是遍历整个矩阵，尝试去找正方形，可能会找到多个，因此还要保留记录那个最大的正方形。

既然是遍历，那么就得从头到尾的进行遍历，假设矩阵matrix大小是M*N，那么就从matrix[0][0]开始进行遍历，一直遍历到matrix[M-1][N-1]。

当遍历到matrix[x][y]时，可以将这个点视为正方形的左上角，以此为基础，去判断matrix[x+1][y]， matrix[x][y+1]， matrix[x+1][y+1]这3个点是否也是1，如果成立，就找到了一个正方形，在此基础上，再向右下方扩展一层，判断能否以matrix[x][y]做正方形的左上角，以matrix[x+2][y+2]做正方形的右下角。

由于总是以某个点做正方形的左上角，因此，最后一行和最后一列是不需要遍历的，因为这些点无法构成正方形的左上角。

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

这个题目非常好的诠释了一句话----“技术，只是实现目标的方式和手段”。

很多人面对问题时，总是有一种较劲脑汁写算法的冲动，还有人，以为每一种问题都有一个成熟的解决方案，似乎接触过这个方案并记忆下来，今后再遇到时就可以迎刃而解了。殊不知，编程是一个创造性的思考过程，很多人不愿意思考，更喜欢走马观花般的背答案。短时间内的确可以提升算法能力，但长期来看，你的逻辑能力才是解决问题的根本，思考才是第一位的。

我们先不去想怎么写算法，而是先分析，抽丝剥茧的对这个问题进行分析。

首先，最左侧的柱子和最右侧的柱子上面不可能存储雨水，这个判断很简单，不做讨论。

其次，每个柱子上能存储多少水，取决于它左右两侧最高柱子的高度，以索引为5的柱子为例，这个柱子的高度是0，它左侧最高的柱子是索引为3的柱子，高度为2， 它右侧最高的柱子是索引为7的柱子，高度为3，这两个柱子的高度决定了，索引为5的柱子上面可以存储水2个单位。

经过上面的两点分析，解题的思路就非常清晰了。

遍历数组，计算每个柱子左右两侧的最高柱子的高度，这两个高度中选最小的，如果这个最小高度大于当前柱子的高度，那么差值就是当前这个柱子能够存储的水的量。

由于遍历的过程是从左向右，因此，左侧最高柱子的高度可以用一个变量保存起来，而右侧最高柱子的高度则需要每次都去计算,但是经过一次寻找后，这个最高柱子的位置就确定了，假设位置为K，对于这个柱子左侧的所有柱子来说，他们右侧的最高柱子都是固定的，因此，也可以存储起来，直到遍历过程中当前柱子的索引大于等于K，则需要重新寻找。

换句话说，第一个字符串的排列之一是第二个字符串的子串

你可以写一个算法，找出一个字符串的所有排列，然后利用字符串的find函数，在第二个字符串中逐个查找是否存在这些排列。

上面的思路虽然笨重，但可以解决问题。

让我们把思路从字符串排列上移开，假如有一个字符串包含了字符串“abc”的6个人排列中的某一个，那么可以肯定的讲，在这个字符串里，一定有一个长度为3的子串，这个子串包含了a,b,c这三个字符。

至于顺序，则完全不用考虑，只要这个长度为3的子串包含了a,b,c这三个字符，那么这个子串就一定是字符串“abc”的某个排列。

统计第一个字符串的字符信息，存放于字典中，记录每个字符的数量
遍历第二个字符串，同样统计每个字符的数量，然后和第一步中的字符信息进行比较，其实就是两个字典的比较。这里有一个需要注意的地方，遍历过程中，只能统计子串的信息，而不是从头到尾的去做统计，如果第一个字符串的长度是3，那么当第二个字符串遍历到索引5时，只能统计索引3到5这个范围内的信息

如果两个字典完全相同，就说明第二个字符串的这段子串是第一个字符串的一个排列