在Java 8中使用嵌套的for循环

Question

我在下面的代码中使用嵌套的for循环，并且有一些条件破坏了内部的for循环，这提高了此代码的性能。

public static int getMaxValue(List<Integer> list) {
    int result = -1;
    for(int i=0; i<list.size(); i++) {
        for(int j=i+1; j<list.size(); j++) {
            if(list.get(j) - list.get(i) <= 0) break;
            if(list.get(j) - list.get(i) > result) {
                result = list.get(j) - list.get(i);
            }
        }
    }
    return result;
}

现在如何使用Java 8流执行相同的逻辑？我想出了以下代码：

public static int getMaxValue(List<Integer> list) {
    int[] result = { -1 };
    IntStream.range(0, list.size()).forEach(i -> {
        IntStream.range(i + 1, list.size()).forEach(j -> {
            if(list.get(j) - list.get(i) <= 0) return;

            if(list.get(j) - list.get(i) > result[0]) {
                result[0] = list.get(j) - list.get(i);
            }
        });
    });
    return result[0];
}

在这里，我无法break在Java流中使用return语句，因此我使用了语句，但是该语句仍在运行内部循环，因为它不会中断它，因此性能不会得到改善。

Answer 1

如果我理解您的代码，您正在尝试查找输入列表中任何两个元素之间的最大成对差异。您可以使用IntSummaryStatistics：

public static int getMaxValue(List<Integer> list) {
    IntSummaryStatistics stats = list.stream()
        .mapToInt(Integer::intValue)
        .summaryStatistics();
    return stats.getMax() - stats.getMin();
}

这是O（n）操作，带有O（1）辅助存储。仍然不需要O（n²）操作。归根结底，尽早突破循环是一种优化，但不是一种很有效的优化方法—找到一种渐近成本较低的方法总是比仅仅早日摆脱循环更为有效。