随机数组求运行最大值时update maximum调用次数及期望问题

咱们先拆解第一个问题，再深入第二个更具体的场景：

问题1：随机化数字数组中，遍历找运行最大值时update maximum的调用次数？ #

首先得明确：这个update次数本质上就是遍历过程中“新的全局最大值出现的次数”——也就是每遇到一个比之前所有元素都大的数，就会触发一次update。

举个简单例子：如果随机数组是[5, 2, 7, 3, 9]，遍历过程中：

• 第一个元素5是初始最大值，触发1次update；
• 2比5小，不触发；
• 7比5大，触发第2次；
• 3比7小，不触发；
• 9比7大，触发第3次；
  总共3次update。

但因为数组是随机化的，这个次数没有固定的确定值，我们通常关注的是多次运行后的平均次数（也就是期望），这就正好对应第二个问题的场景。

问题2：包含-N到N的洗牌数组中，遍历找最大值的update次数期望？ #

首先明确数组的基本信息：数组包含从-N到N的所有整数，总长度L = 2N + 1，所有元素唯一，洗牌后每个排列的出现概率相等。

推导过程（用指示变量法） #

我们可以用线性期望的思路来计算：

1. 定义指示变量X_i（i从1到L）：如果第i个元素是前i个元素中的最大值，X_i = 1，否则X_i = 0。
2. 总update次数X = X_1 + X_2 + ... + X_L，根据线性期望的性质（不管变量是否独立，期望的和等于和的期望），我们只需要计算每个E[X_i]再求和即可。
3. 对于第i个位置：前i个元素是随机排列的，每个元素成为最大值的概率相等，所以E[X_i] = 1/i。

所以总期望就是调和级数的和：

E[X] = 1 + 1/2 + 1/3 + ... + 1/L

近似值说明 #

当数组长度L很大时，调和级数的和可以用自然对数近似：

E[X] ≈ ln(L) + γ

其中γ是欧拉常数（约等于0.5772），当L足够大时，γ的影响相对较小，所以期望会接近ln(array.length)，这和题目里的补充说明一致。

小例子验证 #

比如当N=1时，数组是[-1, 0, 1]，长度L=3，调和级数和为1 + 1/2 + 1/3 ≈ 1.833。我们枚举所有6种排列：

• [-1, 0, 1]：update 3次
• [-1, 1, 0]：update 2次
• [0, -1, 1]：update 2次
• [0, 1, -1]：update 2次
• [1, -1, 0]：update 1次
• [1, 0, -1]：update 1次

平均次数为(3+2+2+2+1+1)/6 = 11/6 ≈ 1.833，和计算结果完全一致。而ln(3) ≈ 1.0986，加上欧拉常数后≈1.6758，已经比较接近；当L增大到1000时，调和级数和约为7.485，ln(1000)+γ≈6.9078+0.5772≈7.485，几乎完全重合。

内容的提问来源于stack exchange，提问作者wz366