Medium

题目描述

给你一个长度为 n 的二进制字符串 s，其中：

  • ‘1’ 表示活跃段
  • ‘0’ 表示非活跃段

你最多可以进行一次交易来最大化 s 中活跃段的数量。在一次交易中，你需要：

  1. 将一个被 ‘0’ 包围的连续 ‘1’ 块转换为全 ‘0’
  2. 然后，将一个被 ‘1’ 包围的连续 ‘0’ 块转换为全 ‘1’

返回进行最优交易后 s 中活跃段的最大数量。

注意：将 s 视为在两端都增加了 ‘1’，形成 t = ‘1’ + s + ‘1’。增加的 ‘1’ 不计入最终计数。

示例 1：

输入：s = "01"
输出：1
解释：因为没有被 '0' 包围的 '1' 块，所以无法进行有效交易。活跃段的最大数量是 1。

示例 2：

输入：s = "0100"
输出：4
解释：
字符串 "0100" → 增强为 "101001"
选择 "0100"，转换 "101001" → "100001" → "111111"
去除增强后的最终字符串是 "1111"。活跃段的最大数量是 4。

示例 3：

输入：s = "1000100"
输出：7
解释：
字符串 "1000100" → 增强为 "110001001"
选择 "000100"，转换 "110001001" → "110000001" → "111111111"
去除增强后的最终字符串是 "1111111"。活跃段的最大数量是 7。

示例 4：

输入：s = "01010"
输出：4
解释：
字符串 "01010" → 增强为 "1010101"
选择 "010"，转换 "1010101" → "1000101" → "1111101"
去除增强后的最终字符串是 "11110"。活跃段的最大数量是 4。

约束条件：

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

解题思路

解题思路

这道题的核心思想是通过一次交易来最大化活跃段（‘1’）的数量。理解题意后，我们需要：

  1. 分析交易规则：首先将被 ‘0’ 包围的连续 ‘1’ 块变为 ‘0’，然后将被 ‘1’ 包围的连续 ‘0’ 块变为 ‘1’
  2. 增强字符串：在原字符串两端添加 ‘1’，这样可以更好地识别被包围的块
  3. 找到最优策略：为了最大化收益，我们需要找到一个被 ‘0’ 包围的 ‘1’ 块，使得删除它后能够连接更多的 ‘0’ 块并将其转换为 ‘1’

关键观察：

  • 当我们删除一个被 ‘0’ 包围的 ‘1’ 块时，这个块两侧的 ‘0’ 块就会连接起来
  • 然后我们可以将这个连接后的大 ‘0’ 块（现在被 ‘1’ 包围）转换为 ‘1’
  • 收益 = 新增的 ‘1’ 数量 - 删除的 ‘1’ 数量

算法步骤：

  1. 统计原字符串中 ‘1’ 的总数
  2. 在增强字符串中找到所有的段（连续的 ‘0’ 或 ‘1’）
  3. 对于每个被 ‘0’ 包围的 ‘1’ 段，计算删除它后能获得的净收益
  4. 选择收益最大的交易，如果没有正收益则不进行交易

代码实现

class Solution {
public:
    int maxActiveSectionsAfterTrade(string s) {
        int n = s.length();
        int originalOnes = 0;
        for (char c : s) {
            if (c == '1') originalOnes++;
        }
        
        // 增强字符串
        string augmented = "1" + s + "1";
        vector<pair<char, int>> segments;
        
        // 分割成段
        char current = augmented[0];
        int count = 1;
        for (int i = 1; i < augmented.length(); i++) {
            if (augmented[i] == current) {
                count++;
            } else {
                segments.push_back({current, count});
                current = augmented[i];
                count = 1;
            }
        }
        segments.push_back({current, count});
        
        int maxDelta = 0;
        
        // 寻找被'0'包围的'1'段
        for (int i = 1; i < segments.size() - 1; i++) {
            if (segments[i].first == '1' && 
                segments[i-1].first == '0' && 
                segments[i+1].first == '0') {
                // 计算收益：左侧0段长度 + 右侧0段长度 - 当前1段长度
                int delta = segments[i-1].second + segments[i+1].second - segments[i].second;
                maxDelta = max(maxDelta, delta);
            }
        }
        
        return originalOnes + maxDelta;
    }
};

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        original_ones = s.count('1')
        
        # 增强字符串
        augmented = '1' + s + '1'
        segments = []
        
        # 分割成段
        current = augmented[0]
        count = 1
        for i in range(1, len(augmented)):
            if augmented[i] == current:
                count += 1
            else:
                segments.append((current, count))
                current = augmented[i]
                count = 1
        segments.append((current, count))
        
        max_delta = 0
        
        # 寻找被'0'包围的'1'段
        for i in range(1, len(segments) - 1):
            if (segments[i][0] == '1' and 
                segments[i-1][0] == '0' and 
                segments[i+1][0] == '0'):
                # 计算收益：左侧0段长度 + 右侧0段长度 - 当前1段长度
                delta = segments[i-1][1] + segments[i+1][1] - segments[i][1]
                max_delta = max(max_delta, delta)
        
        return original_ones + max_delta

public class Solution {
    public int MaxActiveSectionsAfterTrade(string s) {
        int originalOnes = 0;
        foreach (char c in s) {
            if (c == '1') originalOnes++;
        }
        
        // 增强字符串
        string augmented = "1" + s + "1";
        List<(char, int)> segments = new List<(char, int)>();
        
        // 分割成段
        char current = augmented[0];
        int count = 1;
        for (int i = 1; i < augmented.Length; i++) {
            if (augmented[i] == current) {
                count++;
            } else {
                segments.Add((current, count));
                current = augmented[i];
                count = 1;
            }
        }
        segments.Add((current, count));
        
        int maxDelta = 0;
        
        // 寻找被'0'包围的'1'段
        for (int i = 1; i < segments.Count - 1; i++) {
            if (segments[i].Item1 == '1' && 
                segments[i-1].Item1 == '0' && 
                segments[i+1].Item1 == '0') {
                // 计算收益：左侧0段长度 + 右侧0段长度 - 当前1段长度
                int delta = segments[i-1].Item2 + segments[i+1].Item2 - segments[i].Item2;
                maxDelta = Math.Max(maxDelta, delta);
            }
        }
        
        return originalOnes + maxDelta;
    }
}

var maxActiveSectionsAfterTrade = function(s) {
    const originalOnes = (s.match(/1/g) || []).length;
    
    // 增强字符串
    const augmented = '1' + s + '1';
    const segments = [];
    
    // 分割成段
    let current = augmented[0];
    let count = 1;
    for (let i = 1; i < augmented.length; i++) {
        if (augmented[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

其中 n 是字符串的长度。算法需要遍历字符串一次来分割成段，然后遍历所有段来找到最优交易，因此时间复杂度是线性的。空间复杂度主要用于存储段的信息。