如何将寻找左侧更年轻最高力量球员的算法优化至O(NlogN)或O(N)复杂度？

先明确下咱们要解决的问题：
给定一个球员数组（每个元素格式为{id, age, strength}，id等于数组索引），对每个球员，找到数组中在他左侧、年龄比他小的球员里力量最大的那个，将该力量加入结果；如果没有符合条件的球员，结果为-1。

举个例子：
输入：

{ {0, 14, 75}, {1, 17, 65}, {2, 17, 50}, {3, 13, 40}, {4, 16, 90}, {5, 17, 84}, {6, 16, 67} }

对应输出：

{ -1 , 75 , 75 , -1 , 75 , 90 , 75}

你写的O(N²)暴力解法逻辑是完全正确的，能准确得到结果，但当球员数量N很大时（比如1e5级别），双层循环的效率就会跟不上。下面咱们来聊两种O(NlogN)的优化思路，以及为什么O(N)复杂度基本不可行。

优化方案1：O(NlogN) 离线处理 + Fenwick树（前缀Max版） #

这个思路的核心是把问题转化为动态维护年龄对应的最大力量，查询前缀最大力量，用改造后的Fenwick树（二叉索引树）来实现高效的查询和更新。

具体步骤： #

1. 年龄离散化：年龄的取值范围可能很大（比如1到1e9），但球员数量只有N，所以我们可以把所有出现过的年龄去重排序，映射到1~N的连续整数，这样能大幅压缩Fenwick树的空间。
2. 按索引顺序处理每个球员：
   • 对当前球员，先查询Fenwick树中所有小于当前年龄的年龄对应的最大力量，这就是结果res[i]（如果没有符合条件的，结果为-1）。
   • 然后把当前球员的力量更新到Fenwick树的对应年龄位置：如果该年龄已记录的最大力量小于当前力量，就更新它。
3. 改造Fenwick树：标准Fenwick树支持前缀和，这里我们把加法操作改成取max操作，让它支持前缀max查询。

Java代码示例： #

import java.util.*;

public class PlayerStrengthSolver {
    static class FenwickTreeForMax {
        private int[] tree;

        public FenwickTreeForMax(int size) {
            tree = new int[size + 1];
            Arrays.fill(tree, -1); // 初始值设为-1，表示无有效数据
        }

        // 更新：将指定年龄索引对应的最大力量更新为max(现有值, 当前力量)
        public void update(int ageIndex, int strength) {
            while (ageIndex < tree.length) {
                tree[ageIndex] = Math.max(tree[ageIndex], strength);
                ageIndex += ageIndex & -ageIndex;
            }
        }

        // 查询：所有小于等于ageIndex的年龄中，力量的最大值
        public int query(int ageIndex) {
            int maxStrength = -1;
            while (ageIndex > 0) {
                maxStrength = Math.max(maxStrength, tree[ageIndex]);
                ageIndex -= ageIndex & -ageIndex;
            }
            return maxStrength;
        }
    }

    public static int[] findMaxYoungerStrength(int[][] players) {
        int n = players.length;
        int[] result = new int[n];

        // 步骤1：离散化年龄
        List<Integer> allAges = new ArrayList<>();
        for (int[] player : players) {
            allAges.add(player[1]);
        }
        // 去重并排序
        Set<Integer> uniqueAgesSet = new TreeSet<>(allAges);
        List<Integer> uniqueAges = new ArrayList<>(uniqueAgesSet);
        Map<Integer, Integer> ageToIndex = new HashMap<>();
        for (int i = 0; i < uniqueAges.size(); i++) {
            ageToIndex.put(uniqueAges.get(i), i + 1); // Fenwick树从1开始索引
        }

        FenwickTreeForMax ft = new FenwickTreeForMax(uniqueAges.size());

        // 步骤2：按索引顺序处理每个球员
        for (int i = 0; i < n; i++) {
            int currentAge = players[i][1];
            int currentStrength = players[i][2];

            // 找到第一个小于当前年龄的最大索引，查询前缀max
            int ageIdx = Collections.binarySearch(uniqueAges, currentAge);
            if (ageIdx > 0) {
                result[i] = ft.query(ageIdx);
            } else {
                // 没有比当前年龄小的球员
                result[i] = -1;
            }

            // 更新Fenwick树
            int updateIdx = ageToIndex.get(currentAge);
            ft.update(updateIdx, currentStrength);
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] players = {{0, 14, 75}, {1, 17, 65}, {2, 17, 50}, {3, 13, 40}, {4, 16, 90}, {5, 17, 84}, {6, 16, 67}};
        int[] res = findMaxYoungerStrength(players);
        System.out.println(Arrays.toString(res)); // 输出 [-1, 75, 75, -1, 75, 90, 75]
    }
}

这个解法的时间复杂度是O(NlogN)：离散化过程是O(NlogN)，每个球员的查询和更新操作都是O(logN)，总共N次操作，所以整体复杂度是O(NlogN)。

优化方案2：O(NlogN) 平衡BST维护年龄-力量映射 #

你提到的BST思路也是可行的，我们可以用平衡BST（比如Java的TreeSet）维护按年龄排序的（年龄，该年龄最大力量）节点，每次查询小于当前年龄的所有节点中的最大力量，再更新BST。

不过需要注意：TreeSet默认不支持直接查询前缀max，所以我们需要自定义节点比较器，或者结合NavigableSet的方法来实现。这种方式的时间复杂度也是O(NlogN)，但实现起来不如Fenwick树简洁，所以更推荐前者。

关于O(N)复杂度的可能性 #

用单调栈/队列实现O(N)复杂度基本是不可行的。因为单调栈擅长处理基于索引顺序的局部极值问题（比如下一个更大元素），但这个问题的约束是「年龄更小」，而年龄和索引的顺序没有必然联系：后面的球员可能年龄比前面的小，也可能大。单调栈无法同时维护年龄的有序性和索引的顺序性，一旦弹出栈中元素，就会丢失那些年龄大但索引靠前的球员信息，而后续球员可能需要这些信息（如果后续球员年龄更大的话）。所以目前没有已知的O(N)解法。

备注：内容来源于stack exchange，提问作者Turtle