Java流式操作在算法竞赛中的应用

一、Stream API基础概念

1. 什么是Stream

Stream（流）是Java 8引入的一个重要特性，它提供了一种函数式编程的方式来处理集合数据。Stream API让我们可以以声明式的方式处理数据，而不是使用传统的命令式编程方式。在算法竞赛中，合理使用Stream可以让代码更加简洁、易读，同时在某些场景下还能提供不错的性能。

2. Stream的特点

声明式编程：通过描述想要的结果而不是具体的步骤
链式操作：可以将多个操作串联起来
惰性求值：中间操作不会立即执行
并行处理：可以轻松实现并行操作

二、常用Stream操作在竞赛中的应用

1. 数组转换与处理

// 数组转List
int[] arr = {1, 2, 3, 4, 5};
List<Integer> list = Arrays.stream(arr)
    .boxed()
    .collect(Collectors.toList());

// 数组去重
int[] unique = Arrays.stream(arr)
    .distinct()
    .toArray();

// 数组排序
int[] sorted = Arrays.stream(arr)
    .sorted()
    .toArray();

2. 数据过滤与映射

// 过滤偶数
int[] evens = Arrays.stream(arr)
    .filter(x -> x % 2 == 0)
    .toArray();

// 数组元素平方
int[] squares = Arrays.stream(arr)
    .map(x -> x * x)
    .toArray();

// 过滤并转换
List<String> result = Arrays.stream(arr)
    .filter(x -> x > 3)
    .mapToObj(String::valueOf)
    .collect(Collectors.toList());

3. 数值统计

// 求和
int sum = Arrays.stream(arr).sum();

// 最大值
Optional<Integer> max = Arrays.stream(arr)
    .boxed()
    .max(Integer::compareTo);

// 统计信息
IntSummaryStatistics stats = Arrays.stream(arr)
    .summaryStatistics();
System.out.println("平均值: " + stats.getAverage());
System.out.println("最大值: " + stats.getMax());
System.out.println("最小值: " + stats.getMin());
System.out.println("总和: " + stats.getSum());
System.out.println("数量: " + stats.getCount());

三、竞赛中的实际应用场景

1. 处理输入数据

Scanner sc = new Scanner(System.in);
// 读取一行数字并转换为int数组
int[] numbers = Arrays.stream(sc.nextLine().split(" "))
    .mapToInt(Integer::parseInt)
    .toArray();

// 读取多行并处理
List<Integer> lines = Stream.generate(sc::nextLine)
    .limit(n)
    .map(Integer::parseInt)
    .collect(Collectors.toList());

2. 图论问题中的应用

// 邻接表表示的图
List<List<Integer>> graph = new ArrayList<>();

// 获取节点的所有邻居
List<Integer> neighbors = graph.get(node).stream()
    .filter(next -> !visited[next])
    .collect(Collectors.toList());

// 获取入度为0的节点
List<Integer> startNodes = IntStream.range(0, n)
    .filter(i -> inDegree[i] == 0)
    .boxed()
    .collect(Collectors.toList());

3. 组合问题

// 生成所有可能的数字组合
List<List<Integer>> combinations = Stream.of(1, 2, 3, 4)
    .flatMap(i -> Stream.of(5, 6, 7, 8)
        .map(j -> Arrays.asList(i, j)))
    .collect(Collectors.toList());

// 生成指定范围内的数字
List<Integer> range = IntStream.rangeClosed(1, n)
    .boxed()
    .collect(Collectors.toList());

四、性能优化建议

1. 避免不必要的装箱/拆箱

// 不推荐
int sum = Arrays.stream(arr)
    .boxed()
    .mapToInt(Integer::intValue)
    .sum();

// 推荐
int sum = Arrays.stream(arr).sum();

2. 合理使用并行流

// 数据量大且操作独立时使用并行流
int[] result = IntStream.range(0, 1000000)
    .parallel()
    .map(this::heavyComputation)
    .toArray();

3. 避免过度使用流

有些场景下，传统的循环可能更清晰或性能更好：

// 简单循环更好
for (int i = 0; i < n; i++) {
    if (arr[i] > max) max = arr[i];
}

// 不必要的流操作
int max = Arrays.stream(arr)
    .max()
    .getAsInt();

五、实战案例分析

1. 蓝桥杯真题示例

以下是一个处理数字序列的问题示例：

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 读取并处理数据
        int[] result = IntStream.range(0, n)
            .map(i -> sc.nextInt())
            .filter(x -> x % 2 == 0)
            .map(x -> x * 2)
            .sorted()
            .toArray();
        
        // 输出结果
        Arrays.stream(result)
            .forEach(x -> System.out.print(x + " "));
    }
}

2. 复杂数据处理

处理学生成绩统计的例子：

class Student {
    String name;
    int score;
    
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
}

// 处理学生数据
List<Student> students = Arrays.asList(
    new Student("Alice", 85),
    new Student("Bob", 92),
    new Student("Charlie", 78)
);

// 获取成绩大于80的学生名单
List<String> highScoreStudents = students.stream()
    .filter(s -> s.score > 80)
    .map(s -> s.name)
    .collect(Collectors.toList());

// 计算平均分
double avgScore = students.stream()
    .mapToInt(s -> s.score)
    .average()
    .orElse(0.0);