这道题是力扣 LCP 49《环形闯关游戏》目标是求能通关的最小初始积分。核心难点是· 环形结构关卡首尾相邻从任一关卡开始都可以向两边扩展。· 积分增长挑战后积分变为 score | challenge[i]按位或积分只会增加补1不会减少。解题思路分三步1. 核心思路二分答案的“贪心验证”既然要求最小值很容易想到二分答案。但关键在于如何高效验证一个给定的初始积分 m 能否通关。验证的核心贪心策略是从某个开启关卡出发不断向左右两侧“吞噬”能挑战的关卡并更新积分。 过程类似双指针向两边扩展。2. 关键优化预处理“扩展段”直接暴力验证每个起点会超时n 最大 5*10^4。需要预处理优化· 向左扩展预处理 left[i] 和 leftScore[i]表示从关卡 i 出发仅凭关卡 i 的积分能一路向左连续挑战多远以及挑战完这段后的总积分。· 向右扩展同理预处理 right[i] 和 rightScore[i]。这样在验证时一旦积分满足某个关卡的要求就可以直接跳过一整个已预处理的连续段而不是一格一格地走大幅提升效率。3. 确定答案的二进制位因为积分增长是“按位或”可以从最高位开始贪心确定答案的每一位· 先取最大值 max max(challenge)其最高位 bit 必须为 1否则连最大值关卡都挑战不了。· 令 res bit然后从次高位开始逐位尝试· 构造一个候选值 candidate res | (bit - 1)即当前确定的高位不变当前位设为 0后续位全设为 1。· 用验证函数检查 candidate 能否通关。· 如果不行说明当前位必须为 1将 res 的该位置为 1。· 继续检查下一位。---Java 实现代码javaclass Solution {private long[] chal;private int n;private long[] leftScore, rightScore;private int[] leftIdx, rightIdx;public long ringGame(long[] challenge) {this.n challenge.length;this.chal new long[3 * n];// 数组复制三份用于处理环形for (int i 0; i 3 * n; i) {chal[i] challenge[i % n];}preprocess();long max 0;for (long v : challenge) max Math.max(max, v);long bit Long.highestOneBit(max);long res bit;while (bit 0) {bit 1;// 尝试把当前位设为0低位全设为1long candidate res | (bit - 1);if (!check(candidate)) {// 如果不行说明当前位必须为1res | bit;}}return res;}// 预处理每个位置向左/右扩展的边界和积分private void preprocess() {int len chal.length;leftScore new long[len];rightScore new long[len];leftIdx new int[len];rightIdx new int[len];for (int i 0; i len; i) {leftScore[i] chal[i];int j i - 1;while (j 0 chal[j] leftScore[i]) {leftScore[i] | leftScore[j];j leftIdx[j];}leftIdx[i] j;}for (int i len - 1; i 0; i--) {rightScore[i] chal[i];int j i 1;while (j len chal[j] rightScore[i]) {rightScore[i] | rightScore[j];j rightIdx[j];}rightIdx[i] j;}}// 验证初始积分 m 是否能通关private boolean check(long m) {int len chal.length;for (int i n; i 2 * n; i) { // 在复制数组的中间一段选起点if (chal[i] m) continue;long score m | leftScore[i] | rightScore[i];int l leftIdx[i], r rightIdx[i];while (true) {if (r - l n) return true; // 已覆盖所有关卡boolean moved false;if (l 0 chal[l] score) {score | leftScore[l];l leftIdx[l];moved true;}if (r len chal[r] score) {score | rightScore[r];r rightIdx[r];moved true;}if (!moved) break;}// 优化跳过已被覆盖的起点}return false;}}这个解法的核心就是预处理连续可挑战段来加速验证配合按位贪心来确定最小初始积分。代码中用 chal 数组复制三份只枚举中间一段 [n, 2n) 作为起点即可覆盖所有环形起始位置的情况。