最近碰到一个算法题：
班级中有n个同学，每个同学有身高~hi~和~wi~，现将这些同学排成一个队，队中相邻同学需满足体重单调递减、身高递增的性质，求队列可能的最长长度。
递增或递减的性质，容易想到将这些同学以h或w进行相应的排序，这样同学间的相对位置就不再发生变化，唯一变化的是每个位置选与不选的问题。
这里以对体重降序为例，将同学以体重降序排序后，原始问题就转换为给定n个元素的数字，求最长上升子序列长度。
对于转换后的问题，O(n^2)的解法是比较直观的，定义dp[i]表示以位置i为结束点的最长上升子序列长度，不难得到如下代码：
def solve(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(0, i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
O(n^2)的解法往往只是提供了最原始思路，我们需要在此基础上进行算法优化。
仔细思考上述求解过程，会更进一步发现问题的本质：对于任意位置i，需要找到之前小于nums[i]且最大dp[j]（j<i)。一般看到最值问题，容易联想到RMQ数据结构。
是的，没错，但要转换为RMQ面临一个问题—小于nums[i]这个条件；稍微熟悉RMQ数据结构的人，或多或少听过一个概念—离散化，把原始数据进行离散化即可解决小于nums[i]这个条件。
因此，我们可以通过离散化+RMQ数据结构，将这个查找过程从O(n)优化到O(lgn)，最终我们得到了一个o(nlgn)的解法。
但上述的这些分析、解法都不是我想写这篇文章的原因，脑子里始终觉得使用RMQ把问题搞得复杂化了，虽然最终我得到了一个o(nlgn)的解法。
我们在回归到上述分析的这句话上：对于任意位置i，需要找到之前小于nums[i]且最大dp[j]（j<i)。这句话定义了整个问题的本质，不妨换个角度思考，对于当前位置i，影响当前位置决策的位置有没有可能存在某种性质。
来看一个简单的证明题：
假设当前位置为k，k > i，k > j，nums[k] > nums[i]，nums[k] > nums[j]，若有nums[i] <= nums[j]且dp[i] >= dp[j]，则任何时候i比j更优。
我们可以通过反证法来验证，假设以位置k为结束点的最长上升子序列包含位置j，则将位置j替换为位置i，结果不会比当前值差，结论得证。
上面的结论能更进一步的泛化为：
对于任意i、j，若nums[i] <= nums[j]且dp[i] >= dp[j]，则任何时候i比j更优。
有了这个结论，再来看看对问题的求解有什么帮助。
对于前i个元素，有用元素构成的序列必然满足—nums[j] < nums[k] 且dp[j] < dp[k]，j <= i, k <= i，记为性质1
所以，对于求解问题：对于任意位置i，需要找到之前小于nums[i]且最大dp[j]（j<i)，我们只需要维持一个单调队列，队列中元素满足性质1，求解位置i时，只需去队列中查找小于nums[i]的最大值并将当前位置信息插入到队列即可。
由于单调队列存在有序性，所以查找、插入都可在O(lgn)时间内完成。
那么问题又来了，这个队列需要支持快速查找、插入，用什么数据结构比较合适呢。
队列中元素以(nums[i],dp[i])形式保存，插入是个麻烦事，需要保持有序性，那这种数据结构基本上就可以确定为平衡二叉树，平衡二叉树写起来比RMQ数据结构还麻烦，显然与我最初的优化旨意违背，不可取。
这里之所以会选用平衡二叉树，本质在于nums[i]有序性导致插入开销，观察队列中存放的元素(num[i],dp[i])，等等，dp[i]不是保存的以i为结束点的最长上升子序列长度吗，很显然其值域为[1,n],并且这个dp[i]必然是从1开始的连续整数。
所以我们采用逆向思路，队列中元素以(dp[i],nums[i])的形式保存，这样就能将dp[i]映射为数组下标，直接在数组上利用二分查找就能完美解决我们的问题了：
import bisect
def solve(nums):
dp = [0] * len(nums)
dp[0], pos = nums[0], 0
for i in range(1, len(nums)):
if nums[i] > dp[pos]:
pos += 1
dp[pos] = nums[i]
else:
dp[bisect.bisect_left(dp, nums[i], hi=pos)] = nums[i]
return pos + 1
嗯，你没看错，整个代码不到15行，短小、精简、强悍，你值得拥有。。。（oops，我又调皮了）
一点感想
从获知到这个题目到写完这篇文章，花了我大约一天的时间找到我想要的最优解，个人觉得有两个点比较有意思。
一者，如何发现单调性这个性质，除了经验、大胆的假设，暂时没有想到其他的办法，思维有时候就是这么神奇，只能刻意练习，没有捷径可寻。
二者，当发现需要使用平衡二叉树的时候，自己或多或少还是有些沮丧，停滞不前，这种时候，一定要定义清楚问题的本质，才有可能找到新的思路，这部分的优化应了那句”山重水复疑无路，柳暗花明又一村”。
关于如何定义并分析问题，我觉得知乎上厉害的人是怎么分析问题的排名第一高票回答提出的这个模型还是蛮有意思的，在尝试中。。。
最后，整个优化过程让我萌生了另外一个想法：
假设人的生命终点是60岁，那我们需要用60年时间去度过这个过程，而这60年期间，会经历各种各样的事情，如果以时间线罗列这些事情，你会发现这是个O(n)的时间复杂度；最优解中讲述了怎么把O(n)降为O(lgn)方法，我觉得这个方法同样适合生命的轨迹，人一生会经历很多事情，但这些事情中对我们产生价值或有影响的是有限的，我们应当去发现、探索对自身有意义的事情，并做好对应的沉淀，只有通过这种方式来优化自身的生命轨迹，才能可能节省大量不必要浪费的时间来找寻对自己更有意思的事情。
最后，来一句，纵然是举案齐眉，到底意难平。