北京
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. 初始分數：所有
s中為1的位置，直接加對應nums值；2. 允許操作：只能交換相鄰的
0和1（要求左邊是0、右邊是1），可以交換任意次；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對應的數值，堆頂永遠是最小的那個數；
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. 核心邏輯：從右向左遍歷，用最小堆動態保留最大的k個數值（k=原1的數量）；
2. 操作本質：利用規則讓1左移，替換掉更小的數值，實現分數最大化；
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助力您的未來發展。
特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
