java - 如何在 O(N) 时间和 O(C) 空间复杂度中使用 Java 8 流 API 从列表中仅删除一个最大值(最小值)

Question

这是一个代码，用于从列表中仅删除一个最大值(在本例中是第一个，但这无关紧要)。它在时间上是 O(n)，在空间上是 O(n)(超出输入)。

public List<Integer> removeOneOfTheMax(List<Integer> nums) {
    int max = Integer.MIN_VALUE;
    int maxIndex = -1;
    Iterator<Integer> it = nums.iterator();
    for (int i = 0; it.hasNext(); i++) {
        Integer temp = it.next();
        if (max < temp) {
            maxIndex = i;
            max = temp;
        }

    }
    nums.remove(maxIndex);
    return nums;
}

1. 与使用 Java 8 流 API 的方法等效的是什么？我想保留时间和空间的复杂性，所以不允许排序。

2. 实际上，如果将 LinkedList 传递到上面的代码中，空间复杂度将为 O(C)(同样，超过输入)，但据我所知，.stream() 创建了一个额外的数据结构，因此等效的流 API 空间必须至少为 O(N)。如果我错了，请纠正我。

Answer 1

流解决方案可能如下所示:

int maxIndex = IntStream.range(1, nums.size()).reduce(0, (i, j) -> {
    int left = nums.get(i);
    int right = nums.get(j);
    return Integer.max(left, right) == left ? i : j;
});

nums.remove(maxIndex);

下面会有一个Spliterator。

流操作本身不会创建额外的数据结构。