区间合并算法求解球的最大取出数量

思路：

观察题目，可以发现这是一个典型的区间合并问题。我们可以从左往右扫描整个序列，用一个栈来记录已经扫描过的元素，每扫描到一个新元素时，我们判断它是否与栈顶元素相同，如果相同就将栈顶元素出栈，将当前元素与栈顶元素所在区间合并并更新答案，否则将当前元素入栈。最后栈中剩余的元素所在区间也需要合并。

具体实现时，我们可以维护一个数组 $cnt$，其中 $cnt_i$ 表示值为 $i$ 的元素的最右端位置。初始时 $cnt_i$ 全部赋值为 $-1$，表示值为 $i$ 的元素不存在。扫描到一个元素 $a_i$ 时，我们先找到它与之前重复的元素的最右端位置 $r$，即 $r = \max{cnt_{a_j}}$，然后将 $cnt_{a_j}$ 更新为 $i$，表示值为 $a_j$ 的元素最右端位置是 $i$。然后我们判断当前元素是否与栈顶元素相同，如果相同就将栈顶元素出栈，并将 $r$ 更新为栈顶元素所在区间的右端点。否则将当前元素入栈，更新答案为当前元素与 $r$ 之间的元素个数。最后将栈中剩余元素所在区间也合并。

时间复杂度：

整个过程只需要扫描一遍序列，时间复杂度为 $O(n)$。

参考代码：