Google VO 面试真题解析：合并多个有序整数流（Merge Sorted Integer Streams）

Implement a function that merges multiple sorted integer streams into a single sorted list.

interface SortedIntegerStream {int next();      // get the integer from the stream in sorted order (small to large)
    boolean hasNext(); // whether there are integers remaining in the stream}

Example:

// [s1, s2, s3]

public List<Integer> merge(SortedIntegerStream s1, SortedIntegerStream s2) {}

public List<Integer> merge(List<SortedIntegerStream> streams) {}

这道题要求将一个或多个已经按升序排列的整数流合并成一个有序结果列表。核心思路是维护每个流当前指向的最小候选值，通常用最小堆（priority queue）来动态选择全局最小元素；每次弹出一个元素后，再从对应流中取下一个值放回堆中，直到所有流都耗尽。这样可以把多路归并的时间复杂度控制在 O(N log k)，其中 N 是总元素数，k 是流的数量。