水塘抽样（蓄水池抽样算法）

问题描述：

1. 给定一个数组，等概率的返回一个最大值下标，要求：空间复杂度O(1)，只遍历一次数组
2. 给定一个数组，等概率的返回 k 个最大值下标，要求：空间复杂度O(1)，只遍历一次数组

解：
考虑维护一个数组 arr，记录之前遇到的最大值 mx。

• 如果当前元素比 mx 要大，那么更新 mx，并把 arr 清空，并将当前元素下标放入 arr。
• 如果当前元素小于 mx，则跳过。
• 如果当前元素等于 mx：
  • 如果 arr 长度不足 k，则直接将下标放入 arr 尾部
  • 否则取 rd = rand() % (k + 1)
    • 若 rd = k，则 continue
    • 否则，将 arr[rd] 与 当前元素替换

该问题可以简化为，n 个元素等概率抽取 k 个。
对于前 k 个元素，放入的可能性为 1，后面不被抽走的可能性为
对于后面放入的元素，也是同理。

LC 题目：https://leetcode-cn.com/problems/linked-list-random-node/