通用建议：题目一般只给一两个输入示例，这是远远不够的。我们思考的时候经常会被示例给束缚（脑子里只对着那个示例想）。如果自己在做题的时候，在纸上多构造几个示例，对比（找不同）和归纳（找相同），会大大增加解决的概率。

思路就是，每次划分（将数组小于等于pivot和大于pivot的元素分开）的时候，用一个慢指针和一个快指针。每当快指针扫描到小于等于pivot的元素，就将这个元素丢到慢指针的位置（同时慢指针增加）。慢指针指向的元素以及其左边的元素，全都是被快指针丢过来的（也就是小于等于pivot的）。

一开始，我尝试通过枚举所有左右边界，来依次计算夹在其中的最高矩形的面积，但是很快发现这种方式非常低效。由于左右边界没有提供关于高度的信息，每次枚举出一对左右边界以后，还要遍历两个边界之间的所有条形（O(n)），才能找出矩形可以达到的最大高度。并且，所有左右边界的组合达到n^2量级。总的时间复杂度将达到O(...

题目链接：[链接]从表面上看，题目问有多少种方式为表达式增加括号，实际上等价于找出表达式所有可能的计算次序，每一种画括号的方式一一对应于一种计算次序。

在上一篇题解中，我们介绍了如何通过在扫描输入的过程中维护一个有序的数据结构来为新输入的计算提供信息。但是我们同时也发现，支持相关操作的容器（既能够进行二分查找又能够在常数时间内插入元素）似乎没有；如果自己构造一棵二叉搜索树，也会烦恼于树的平衡问题。

最直接的方法，拿到一个数x以后，依次遍历x右边的所有数并与x比较，对小于x的数字进行计数，计数的结果就是在x右边、比x小的数字。容易看出，这个方案的时间复杂度是O(n^2)，不是很理想。上面方法对时间的浪费体现在：完全没有利用已经计算得到的信息，把所有可以做的比较都做了一遍。如果我们在拿到x之前已经通过比较知...

如何使我们的枚举能够不重复、不遗漏呢？要做到不重不漏地枚举，我们需要为每一种可能枚举出的元素定义一种“大小判断”，然后定义“如何从一个元素求出稍微大一些的下一个元素”（从当前的枚举迁移到下一个枚举）。最后，我们只要从最小到最大按序枚举，就能够保证不重不漏。

为了使用动态规划算法，要先将父问题分解成子问题（父问题和子问题是同一种问题，只不过分解得到的子问题规模更小）。那么现在就需要我们找出父问题和子问题之间的转移关系。推导父子问题之间的转移关系有2中思路：

在上一篇博客中，我们介绍了最长递增子序列（LIS）问题的一个动态规划算法，时间复杂度为O(n^2)（如果使用二叉树能降低到O(nlogn)）。在这篇文章我们再分析一个O(nlogn)的巧妙算法。思路来自：[链接]

这也属于搜索问题。我们首先想象最长递增子序列（LIS）具有什么样的特征，然后根据这种特征来扫描输入。如果存在某个数字X比某个已有的递增子序列的最后一个元素E要大，且X在E的右边，那么X就可以添加到这个递增子序列的末尾，从而使递增子序列的长度更大。等等，某个已有的递增子序列又是哪个子序列呢？我们希望，这个...

题目连接：[链接]如果只是从数组的左边扫描到右边，不可能在这种单向扫描时知道：在当前扫描到的的地板上方能够装多少水。因为能装多少水依赖于当前地板的两边的地形，而单向扫描时无法知道当前地板右边的地形。因此我们需要从两边向中间扫描。

经过思考，难点主要在于*究竟应该匹配多少个字符。因为*并不是匹配越多字符越好（不能贪婪匹配）：比如模式a*abc中的a*只能匹配aaabc的aa。如果a*匹配了aaa，那么剩余的模式abc（a*abc减去开头的a*）就无法匹配剩余的字符串'bc'。换一种说法，如果a*匹配3个a，a*a（4个a）无法匹配aaabc的任何前缀。同理，如果匹配的字符...

题目分析 题目链接：31. Next Permutation 这题让我们找到比输入数字排列恰好大一点点的数字排列。对这个问题的算法不仅适用于数字串，而且适用于任何有字典序的符号串。 为了方便讨论，我们将输入数字串称为串1，输出数字串称为串2。 输出的串2需要满足以下条件： 字典序增大。字典序增大当且仅当：串2与串1从最高位的...

输入的字符串s由'('和')'组成，其中存在一些子串是合法的括号字符串。比如(()())是合法的括号字符串；()())(())就不是合法的括号字符串，但是其中的()()和(())是合法的括号字符串。

搜索最佳结果的一个一般思想：先想象这个最佳结果必定具有什么样的特征，然后我们通过这些特征来查找，不断找出很多“候选最佳结果”，最后从这些候选结果中选拔出最佳的结果。

搜索最佳结果的一个一般思想：先想象这个最佳结果必定具有什么样的特征，然后我们通过这些特征来查找，不断找出很多“候选最佳结果”，最后从这些候选结果中选拔出最佳的结果。

不难分析出，最大的路径是“^型”的，从一个最高点向下延伸的两条路径组成一个“^型”路径。注意这个“最高点”不一定是树的根。并且，这两条路径必定分别经过左右子节点，并且是向下路径中权值最大的。由于每个节点都有可能是“最高点”，因此对于每个节点（可以用DFS/BFS遍历每个节点），我们都要计算出以该节点为“最高点”的最...

这道题目主要难点在于这样一个问题：a, b, c, d, e, f, c, g, h, ...我从第一个字符开始检查，已经检查到f了，目前为止还没有出现重复字符：[a, b, c, d, e, f,] c, g, h, ...检查到下一个c时，发现它在前面已经出现过了（至于如何判断新字符是否已经出现过，我们在下面讨论）：[a, b, c, d, e, f, c,] g, h, ...这时应...

不断取出值最小的那个Node（因为每个list已经排序，所以这一步只需要找出最小的head Node），添加到已排序链表的尾部，直到所有lists的所有Node都取完。

leetcode题目链接设给出的两个已从小到大排序的数组为nums1和nums2，size1=nums1.size()，size2=nums2.size()。分析题目可以知道，要找到中位数，最好能从2个已排序数组中找到第k小的数字，后者是更具一般性的问题。