给定一个玩家列表，对于每个玩家，找到他左边实力最高的年轻玩家

Question

假设我们有如下的玩家列表

Player format = {id, age, strength}

Input format = { player1, player2, ....}

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

给定上面的输入，对于每个玩家，找到他左边具有最高强度的年轻玩家，并将该强度添加到结果 else -1 中，为了简单起见，我们可以假设玩家 id 与数组的索引相同

对于上述输入，输出为

Output : { -1 , 75 , 75 , -1 , 75 , 90 , 75}

我的方法是O(N^2):

int[] findStrengths() {
    int[][] players = new int[n][3];
    int[] res = new int[n];
    Arrays.fill(res, -1);
    for(int i=0;i<n;i++) {
        for(int j=0;j<i;j++) {
            if(players[j][1] < players[i][1]) {
                res[i] = Math.max(res[i], players[j][2]);
            }
        }
    }
    return res;
}

是否可以使用某种 BST 结构在 O(Nlog(N)) 中解决这个问题，或者使用单调堆栈/队列在 O(N) 中解决这个问题？

Answer 1

这可以通过创建自平衡树在 O(nlogn) 中解决，例如修改后的AVL树以年龄作为节点值，但每个节点还在其子树中存储最大强度。可以创建这样一棵树并且仍然能够以 O(logn) 的时间插入。最简单的方法是采用现有的 AVL 树实现并对其进行修改。如果你有，你可以从左到右检查并通过沿着需要 O(logn) 的树向下查找满足年龄标准的最大强度，然后将玩家插入树中并继续。