构造最高得分平衡括号序列的O(nlogn)及以下复杂度解法咨询

核心思路 #

使用反悔贪心+堆的方案，时间复杂度O(n logn)，完全适配题目给定的1e5数组长度限制。
这个问题的本质可以转化为：选择若干对下标(i,j)满足i<j，每个下标最多属于一个对，最大化总和sum(A[i] - A[j])——每对匹配的左括号i和右括号j刚好贡献A[i]-A[j]，跳过的元素无贡献。

具体实现步骤 #

• 维护一个最大堆存储已选择的右括号的A值，维护两个变量：总得分res，当前括号平衡值balance（左括号数 - 右括号数）。
• 遍历数组中每个元素x = A[i]：
  1. 先默认将当前元素作为右括号处理：res += -x，balance -= 1，将x推入最大堆。
  2. 如果balance < 0，说明右括号数量过多，需要撤销最不划算的一个右括号操作：
     • 弹出堆中最大的x（这个x作为右括号的贡献最小，-x最小）。
     • 如果x > 0：将其转为左括号收益更高，res += 2 * x（原来贡献是-x，转为左括号贡献是+x，差值为2x），balance += 2。
     • 如果x <= 0：直接跳过该元素即可，res += x（原来贡献是-x，转为无贡献差值为x），balance += 1。
• 遍历结束后如果balance > 0，说明有多余的左括号，我们需要撤销贡献最小的左括号（即A值最小的左括号），每撤销一个res -= x，balance -= 1，直到balance == 0。

示例验证 #

以数组[3,1,2]为例：

1. 遍历到3：默认当右括号，res=-3，balance=-1，触发撤销逻辑。3>0转左括号，res=-3 + 2*3=3，balance=-1+2=1。
2. 遍历到1：默认当右括号，res=3-1=2，balance=0。
3. 遍历到2：默认当右括号，res=2-2=0，balance=-1，触发撤销逻辑。弹出最大x=2，直接跳过，res=0+2=2，balance=0。
   最终得分为2，对应最优操作：3放左括号，1放右括号，跳过2，符合预期。

复杂度说明 #

每个元素最多入堆、出堆各一次，堆单次操作时间为O(logn)，整体时间复杂度为O(n logn)，空间复杂度为O(n)，可以轻松处理1e5规模的输入。

内容的提问来源于stack exchange，提问作者unglinh279