Medium

题目描述

给你一个长度为 n 的整数数组 nums 和一个相同长度的二进制字符串 s。

初始时，你的分数是 0。每个索引 i，如果 s[i] = '1'，则会将 nums[i] 贡献给分数。

你可以执行任意次数的操作（包括零次）。在一次操作中，你可以选择一个索引 i，使得 0 <= i < n - 1，其中 s[i] = '0' 且 s[i + 1] = '1'，然后交换这两个字符。

返回一个整数，表示你能达到的最大可能分数。

示例 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。这是能达到的最大分数。

示例 2：

输入：nums = [4,7,2,9], s = "0000"
输出：0
解释：
s 中没有 '1' 字符，所以无法执行交换。分数保持为 0。

约束：

  • n == nums.length == s.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= 10^9
  • s[i] 是 ‘0’ 或 ‘1’

解题思路

这道题的核心思路是贪心算法结合优先队列（最大堆）。

首先理解题目：我们只能将字符串中的 ‘1’ 向左移动（通过 “01” → “10” 的交换），但不能向右移动。这意味着每个 ‘1’ 最终能到达的最左边位置是有限制的。

解题思路：

  1. 观察交换规则：只能执行 “01” → “10” 的交换，这意味着 ‘1’ 只能向左移动，遇到其他 ‘1’ 时会被阻挡。

  2. 贪心策略：为了最大化分数，我们希望让数值较大的位置放上 ‘1’。由于 ‘1’ 只能向左移动，我们可以从左到右遍历，维护一个最大堆来存储当前可用的最大数值。

  3. 具体算法：

    • 从左到右遍历字符串
    • 遇到 ‘0’ 时，将对应的 nums[i] 加入最大堆（表示这个位置可以被后面的 ‘1’ 占据）
    • 遇到 ‘1’ 时，如果堆不为空，就取出堆顶的最大值加到结果中；否则使用当前位置的值

  4. 为什么这样是正确的：每个 ‘1’ 都会选择它能到达的最左边位置中数值最大的那个，这样能保证总分数最大。

时间复杂度为 O(n log n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    long long maximumScore(vector<int>& nums, string s) {
        priority_queue<int> pq;
        long long score = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (s[i] == '0') {
                pq.push(nums[i]);
            } else {
                if (!pq.empty()) {
                    score += pq.top();
                    pq.pop();
                } else {
                    score += nums[i];
                }
            }
        }
        
        return score;
    }
};

class Solution:
    def maximumScore(self, nums: List[int], s: str) -> int:
        import heapq
        max_heap = []
        score = 0
        
        for i in range(len(nums)):
            if s[i] == '0':
                heapq.heappush(max_heap, -nums[i])  # Python uses min heap, so negate for max heap
            else:
                if max_heap:
                    score += -heapq.heappop(max_heap)
                else:
                    score += nums[i]
        
        return score

public class Solution {
    public long MaximumScore(int[] nums, string s) {
        var pq = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
        long score = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            if (s[i] == '0') {
                pq.Enqueue(nums[i], nums[i]);
            } else {
                if (pq.Count > 0) {
                    score += pq.Dequeue();
                } else {
                    score += nums[i];
                }
            }
        }
        
        return score;
    }
}

var maximumScore = function(nums, s) {
    const n = nums.length;
    const arr = s.split('');
    
    // Keep swapping to move 1s to positions with higher values
    let changed = true;
    while (changed) {
        changed = false;
        for (let i = 0; i < n - 1; i++) {
            if (arr[i] === '0' && arr[i + 1] === '1' && nums[i] > nums[i + 1]) {
                arr[i] = '1';
                arr[i + 1] = '0';
                changed = true;
            }
        }
    }
    
    let score = 0;
    for (let i = 0; i < n; i++) {
        if (arr[i] === '1') {
            score += nums[i];
        }
    }
    
    return score;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(n)

其中 n 是数组的长度。时间复杂度主要来自优先队列的插入和删除操作，每次操作的时间复杂度是 O(log n)，最多进行 n 次操作。空间复杂度来自优先队列最多存储 n 个元素。