随机序列中特定规则生成的递减子序列的期望长度化简与渐近行为分析
咱们先把问题再明确一遍：给定n个不同的数随机打乱成序列A，我们先选整个序列的最大值x₁，接着在x₁后面的子序列里选最大的x₂，再在x₂后面的子序列里选最大的x₃，直到没有元素为止，得到递减序列X。现在要算X的长度k的期望，还要化简公式、分析n趋向无穷时的渐近行为。
先看几个直观的例子加深理解：
- 序列A = [1,5,4,2,3]，X = [5,4,3]，长度k=3
- 序列A = [4,3,2,1,5]，X = [5]，长度k=1
- 序列A = [5,1,3,2,4]，X = [5,4]，长度k=2
- 序列A = [3,2,4,5,1]，X = [5,1]，长度k=2
注意：这个X和最长递减子序列不一样，最长递减子序列的期望长度大概是2√n，和咱们这个问题的结果差异很大。
期望公式的化简：用指示变量轻松搞定
原来的概率公式看起来有点复杂，咱们换个更直观的视角：X中的每个元素，其实都是序列某个后缀的最大值。比如x₁是整个序列（后缀1到n）的最大值，x₂是x₁位置之后的后缀的最大值，x₃又是x₂位置之后的后缀的最大值，以此类推。
基于这个观察，我们定义指示变量I_i（i从1到n）：
- 如果序列A中第i个位置的元素是从i到末尾的后缀的最大值，那么I_i=1
- 否则I_i=0
这样X的长度k就等于所有I_i的和：k = I₁ + I₂ + ... + Iₙ。根据期望的线性性，不管变量是否独立，期望的和等于和的期望，所以：
$$E[k] = E[I₁ + I₂ + ... + Iₙ] = \sum_{i=1}^n E[I_i]$$
接下来算每个E[I_i]，也就是第i个位置的元素是后缀i到n的最大值的概率。因为序列是随机排列的，后缀i到n共有L = n - i + 1个元素，每个元素成为这个后缀最大值的概率是相等的，都是1/L。比如：
- 当i=n时，后缀只有自己，概率是1/1=1
- 当i=n-1时，后缀有2个元素，每个是最大值的概率是1/2
- ...
- 当i=1时，后缀是整个序列，每个元素是最大值的概率是1/n
把这些概率加起来，就得到：
$$E[k] = \sum_{L=1}^n \frac{1}{L} = H_n$$
这里H_n就是第n个调和数，也就是1 + 1/2 + 1/3 + ... + 1/n。这就把原来复杂的期望公式化简成了非常简洁的调和数形式！
渐近行为分析（n→∞时）
调和数H_n的渐近展开式是经典的结论：
$$H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + o\left(\frac{1}{n^2}\right)$$
其中γ≈0.5772是欧拉-Mascheroni常数，是一个固定的无理数。
当n趋向于无穷大时，后面的1/(2n)、1/(12n²)等项相对于ln n可以忽略不计，所以我们可以近似认为：
$$E[k] \sim \ln n$$
也就是说，当序列长度n很大时，X的期望长度大约等于n的自然对数，增长速度非常缓慢（比多项式增长慢得多）。
关联滑动窗口最大值的空间复杂度
你提到这个问题来自滑动窗口最大值的单调队列空间分析：当窗口大小为n时，单调队列中维护的元素正好就是咱们这里的X序列。所以单调队列的平均空间复杂度就是这个期望长度H_n，当n很大时近似为ln n，这说明单调队列的平均空间开销是很小的，即使窗口很大也不会快速增长。
备注：内容来源于stack exchange，提问作者maplemaple
