字符串根据前缀查询最大值

假设有一个字符串数组，每个字符串都有一个整数值，现在需要根据给定的前缀查询该前缀下所有字符串的整数值中的最大值。

可以使用前缀树（Trie）来解决这个问题。首先将所有字符串插入前缀树中，同时在每个节点上记录以该节点为结尾的所有字符串的整数值的最大值。然后在查找给定前缀的过程中，沿着前缀树找到该前缀的最后一个节点，该节点上记录的整数值的最大值即为所求。

具体实现可以参考以下代码（Java实现）：

class TrieNode {
    Map<Character, TrieNode> children;
    int maxVal; // 以该节点为结尾的所有字符串的整数值的最大值

    public TrieNode() {
        children = new HashMap<>();
        maxVal = Integer.MIN_VALUE;
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word, int val) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.maxVal = Math.max(node.maxVal, val);
    }

    public int search(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return -1; // 没有找到前缀
            }
            node = node.children.get(c);
        }
        return node.maxVal; // 返回以该节点为结尾的所有字符串的整数值的最大值
    }
}

// 示例用法
String[] words = {"abc", "ab", "bcd", "def", "abcd"};
int[] vals = {5, 3, 8, 6, 7};
Trie trie = new Trie();
for (int i = 0; i < words.length; i++) {
    trie.insert(words[i], vals[i]);
}
System.out.println(trie.search("ab")); // 输出: 5
System.out.println(trie.search("bc")); // 输出: 8
System.out.println(trie.search("de")); // 输出: 6
System.out.println(trie.search("a"));  // 输出: 7