2026-04-29：二进制交换后的最大分数。用go语言，给定一个长度为 n 的整数数组 nums 和一个长度相同的二进制字符串 s。 初始得分为 0。对

2026-04-29：二进制交换后的最大分数。用go语言，给定一个长度为 n 的整数数组 nums 和一个长度相同的二进制字符串 s。

初始得分为 0。对于字符串中每个位置上字符为 '1' 的下标 i，分数都会加上 nums[i]。

你可以进行任意次操作，也可以一次都不做。每次操作时，可以选择一个位置 i（0 <= i < n - 1），要求 s[i] = '0' 且 s[i + 1] = '1'，然后把这两个字符交换。

请计算并返回经过这些操作后，能够得到的最高分数。

n == nums.length == s.length。

1 <= n <= 100000。

1 <= nums[i] <= 1000000000。

s[i] 是 '0' 或 '1'。

输入： nums = [2,1,5,2,3], s = "01010"。

输出： 7。

解释：

我们可以执行以下交换操作：

在下标 i = 0 处交换："01010" 变为 "10010"

在下标 i = 2 处交换："10010" 变为 "10100"

下标 0 和 2 包含 '1'，贡献的分数为 nums[0] + nums[2] = 2 + 5 = 7。这是可以获得的最大分数。

题目来自力扣3781。

解题过程详细解析

先明确核心规则：

1. 1. 初始分数：所有s中为1的位置，直接加对应nums值；

2. 2. 允许操作：只能交换相邻的0和1（要求左边是0、右边是1），可以交换任意次；

3. 3. 本质：1可以向左移动到任意0的位置（因为多次相邻交换能让1持续左移），我们的目标是：让1停在数值最大的位置上，最大化总分。

输入示例：
nums = [2, 1, 5, 2, 3]，s = "0 1 0 1 0"（下标0~4）
初始s中1的位置：下标1、下标3。

一、整体解题思路

我们从右向左遍历数组（从最后一个元素往第一个元素走），配合最小堆实现最优选择：

1. 1. 最小堆的作用：存储当前已选中的1对应的数值，堆顶永远是最小的那个数；

2. 2. 遍历规则：

• • 遇到s[i]='1'：必须选这个位置，数值加入总分，同时放入最小堆；

• • 遇到s[i]='0'：这个位置可以放一个1（因为1能左移过来），如果当前位置的数值 > 堆里最小的数，就替换：用更大的数替换堆里最小的数，总分也同步更新（只加差值）；

3. 最终堆里保留的就是k个最大的数（k是原字符串中1的个数），总和就是最大分数。

二、分步骤详细过程（对应示例遍历）

原数组：下标0(2)、下标1(1)、下标2(5)、下标3(2)、下标4(3)
原字符串：0、1、0、1、0
原1的数量：2个（最终必须选2个位置放1）
遍历方向：从下标4 → 下标0

步骤1：遍历下标4（数值3，s='0'）

• • 当前堆为空，没有可以替换的数，不做任何操作。

• • 这是必须选的1，总分 +=2（当前总分=2）；

• • 把数值2放入最小堆，堆：[2]（堆顶是2）。

• • 这是0的位置，可以放1；

• • 比较：当前数5 > 堆顶最小值2；

• • 执行替换：总分 += 5-2 =3（总分=2+3=5）；

• • 用5替换堆顶的2，堆调整为[5]（堆顶是5）。

• • 这是必须选的1，总分 +=1（当前总分=5+1=6）；

• • 把数值1放入最小堆，堆：[1,5]（堆顶是最小的1）。

• • 这是0的位置，可以放1；

• • 比较：当前数2 > 堆顶最小值1；

• • 执行替换：总分 +=2-1=1（总分=6+1=7）；

• • 用2替换堆顶的1，堆调整为[2,5]（堆顶是2）。

遍历结束，总分=7，和题目示例输出完全一致。
最终选中的两个位置：下标0（2）、下标2（5），总和2+5=7。

四、复杂度分析 1. 时间复杂度

• • 遍历数组：O(n)（n是数组长度，每个元素仅遍历一次）；

• • 堆操作：每个元素最多入堆、出堆、调整堆各一次，堆的大小最大为k（原1的个数），单次堆操作O(logk)；

• • 总时间复杂度：O(n log n)（logk ≤ logn，是最优可接受复杂度）。

• • 仅使用了一个最小堆存储元素，堆的最大空间为k（原1的个数）；

• • 总额外空间复杂度：O(n)（最坏情况全是1，堆大小为n）。

1. 1. 核心逻辑：从右向左遍历，用最小堆动态保留最大的k个数值（k=原1的数量）；

2. 2. 操作本质：利用规则让1左移，替换掉更小的数值，实现分数最大化；

3. 3. 复杂度：时间O(n log n)，空间O(n)，能高效处理n≤1e5的大数据量。

package main

 import (
    "container/heap"
    "fmt"
    "sort"
)

 func maximumScore(nums []int, s string) (ans int64) {
    h := hp{}
    // Traverse from the end to the beginning
    for i := len(nums) - 1; i >= 0; i-- {
        x := nums[i]
        if s[i] == '1' {
            ans += int64(x)
            heap.Push(&h, x)
        } elseif h.Len() > 0 && x > h.IntSlice[0] {
            ans += int64(x - h.IntSlice[0])
            h.IntSlice[0] = x
            heap.Fix(&h, 0)
        }
    }
    return
}

 type hp struct{ sort.IntSlice }

 func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (hp) Pop() (_ any)  { return }

 func main() {
    nums := []int{2, 1, 5, 2, 3}
    s := "01010"
    result := maximumScore(nums, s)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import heapq

 def maximumScore(nums, s):
    ans = 0
    h = []  # min heap
    # Traverse from the end to the beginning
    for i in range(len(nums) - 1, -1, -1):
        x = nums[i]
        if s[i] == '1':
            ans += x
            heapq.heappush(h, x)
        elif h and x > h[0]:
            ans += x - h[0]
            heapq.heapreplace(h, x)  # pop smallest and push x
    return ans

 def main():
    nums = [2, 1, 5, 2, 3]
    s = "01010"
    result = maximumScore(nums, s)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  

  


 using namespace std;

 long long maximumScore(vector& nums, string s) {
    long long ans = 0;
    // Min heap using greater 
 
    priority_queue, greater> pq;

     // Traverse from the end to the beginning
    for (int i = nums.size() - 1; i >= 0; i--) {
        int x = nums[i];
        if (s[i] == '1') {
            ans += x;
            pq.push(x);
        } elseif (!pq.empty() && x > pq.top()) {
            ans += x - pq.top();
            pq.pop();
            pq.push(x);
        }
    }
    return ans;
}

 int main() {
    vector nums = {2, 1, 5, 2, 3};
    string s = "01010";
    long long result = maximumScore(nums, s);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。