2025-09-23：操作后最大活跃区段数Ⅰ。用go语言，给定一个长度为 n 的二进制字符串 s，其中字符 ‘1‘ 代表“活跃”

福大大架构师每日一题

发布于 2025-12-18 12:49:03

1230

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-09-23：操作后最大活跃区段数Ⅰ。用go语言，给定一个长度为 n 的二进制字符串 s，其中字符 '1' 代表“活跃”区间，'0' 代表“非活跃”区间。你最多可以做一次如下复合操作以使字符串中活跃区间的数量尽可能多：

• 先把某一段两端均为 '0' 的连续 '1' 全部改为 '0'；
• 再把某一段两端均为 '1' 的连续 '0' 全部改为 '1'。

最后返回在最佳选择下，s 中活跃区间（即连续 '1' 段）的最大可能个数。

提示：为便于处理，在字符串两端分别加上一个 '1'（形成 t = '1' + s + '1'），这两个额外的 '1' 不计入最终结果。

1 <= n == s.length <= 100000。

s[i] 仅包含 '0' 或 '1'。

输入： s = "01"。

输出： 1。

解释：

因为没有被 '0' 包围的 '1' 区块，因此无法进行有效操作。最大活跃区段数为 1。

题目来自力扣3499。

解决思路

1. 问题理解与操作分析：
- • 操作1（'1' 变 '0'）：此操作会减少一段活跃区间（因为一段连续的 '1' 被移除），但为后续操作2创造条件。它只能作用于被 '0' 包围的连续 '1'（即该段 '1' 的前后都是 '0'）。
- • 操作2（'0' 变'1'）：此操作是增加活跃区间的关键。它只能作用于被'1'包围的连续'0'（即该段'0'的前后都是'1'）。操作后，这段'0'会变成'1'，可能连接其前后的'1'区段，从而形成一个更大的连续'1'区段，或者直接增加一段新的'1'。
- • 复合操作的意义：先执行操作1（移除一段被 '0' 包围的 '1'）可能会为操作2创造新的条件（使得一段原本不被 '1' 包围的 '0' 变成被 '1' 包围）。然而，根据题目描述和常见解法，更直接有效的方法是寻找相邻的两段 '0'，通过操作2将它们变为 '1'，从而可能连接其周围的 '1' 区段。操作1在此上下文中通常并非必需，因为最终目标是最大化 '1' 的数量。
2. 关键观察：
- • 字符串经过两端添加 '1' 后（t = '1' + s + '1'），原问题转化为在字符串 t 中寻找机会。
- • 活跃区间的数量最终由连续 '1' 段的数量决定。我们的目标是最大化这个数量。
- • 操作2的有效目标：只有那些两端都是 '1'的连续'0'段才能被变为'1'。将这样的一段'0'变为'1'后，可能会将其前后的两段'1'连接成一段（减少一个区段），但也可能因为填补了'0'的间隙而使得原本被隔开的'1'段连接起来，同时如果这段 '0' 本身位于一个较长的 '0' 序列中，改变它可能不会改变区段总数。然而，更常见且有益的情况是，将一段这样的'0'变为'1'后，有时可以增加一个新的活跃区段（例如，当这段'0'单独存在且被'1'包围时），但更重要的是，它可能连接多个 '1' 区段。
- • 实际上，最优操作往往是将一段连续的 '0' 变为 '1'，并且寻找相邻的两段 '0' 是一个常见的优化点。通过一次操作将相邻的两段 '0' 变为 '1'，可以显著改变区段的连接情况。
3. 算法过程详细描述：
- • 预处理：在字符串 s 的首尾添加字符 '1'，得到新字符串 t。这两个额外的 '1' 用于简化边界条件处理，确保在考虑连续 '0' 段时，其两端总是 '1'（因为字符串最左和最右现在都是 '1'）。
- • 遍历与分段：遍历字符串 t，将其划分为连续的 '0' 段和 '1' 段。记录每一段的字符类型（'0' 或 '1'）及其长度。
- • 初始活跃区段数：统计字符串t中连续'1'段的数量（记为ans）。由于我们在首尾添加了'1'，需要注意到最初的s中可能首尾就是'1'，但添加的'1'不计入最终结果，所以初始活跃区段数可能需要根据原字符串s的实际情况计算，不过算法中通常直接处理t 然后减去边界影响或通过其他方式调整。
- • 寻找最优操作机会：
  - • 操作的核心是将一段两端均为 '1' 的连续 '0' 变为 '1'。
  - • 遍历所有的连续 '0' 段，但只考虑那些两端都是 '1' 的段（在字符串 t 中，由于首尾都有 '1'，所有的 '0' 段理论上都满足两端是 '1'，但需要注意段与段之间的关系）。
  - • 重点：寻找相邻的两段 '0'。这是因为将相邻的两段'0'变为'1'，可以产生最大的效益。例如，假设有三段：'1'、'0'、'1'、'0'、'1'。如果将中间的两段'0'都变为'1'，那么原本的三段'1'会连接成一段，但同时，由于我们改变了两段'0'，这个操作本身可能会增加一个新的活跃区段，或者更常见的是，它连接了多个段，从而减少了活跃区段的总数？这里需要仔细分析：操作2将一段'0'变为'1'后，可能会将其前后的'1'连接起来，从而减少活跃区段的数量（因为两段'1'合并为一段）。但是，问题的目标是最大化活跃区段的个数，而不是最大化 '1' 的连续长度。因此， sometimes 连接段反而会减少段的数量，这与目标相反。
- • 重新理解问题：活跃区段的“数量”是指连续 '1' 段的个数，而不是 '1' 的总数。因此，将一段 '0' 变为 '1'：
  - • 如果这段 '0' 连接着两个 '1' 段，那么操作后这三个段会合并成一个段（段数减少1）。
  - • 如果这段 '0' 只与一个 '1' 段相邻（例如在字符串的端点，但由于我们添加了边界 '1'，这种情况不存在），或者它本身处于一个孤立的位置，操作后可能会增加一个新的段。
- • 策略调整：由于操作2可能减少活跃区段的数量（合并段），而我们的目标是增加段的数量，因此最优操作通常不是去连接段，而是去创建新的段。这就需要利用操作1先移除一段被 '0' 包围的 '1'，然后再利用操作2将一段被 '1' 包围的 '0' 变为 '1'。
  - • 操作1（移除一段 '1'）会减少一个活跃区段。
  - • 操作2（增加一段 '1'）可能会增加一个活跃区段（如果这段 '0' 是孤立的）或减少段数（如果它连接了段）。
  - • 复合操作的整体效果需要计算。
- • 常见解法（基于搜索结果）：根据搜索结果，更高效的思路是：
  - • 直接寻找相邻的两段 '0'，其总长度代表了通过操作可以产生的最大增益。最终的最大活跃区段数为初始的 '1' 段数加上这个最大增益（ans + mx）。
  - • 具体来说：
    - • 初始化变量 mx 用于记录相邻两段 '0' 的最大总长度，pre0 用于记录前一段 '0' 的长度，cnt 用于计数当前段的长度。
    - • 遍历字符串 t，统计连续相同字符的段。
    - • 遇到 '1' 段时，将其长度加到 ans（初始活跃区段数）中。
    - • 遇到 '0' 段时，计算当前 '0' 段长度与前一段 '0' 段长度（pre0）的和，并更新 mx。然后将 pre0 更新为当前 '0' 段的长度。
  - • 最终结果为 ans + mx。
- • 为什么是相邻两段 '0'：因为通过操作将相邻的两段 '0' 变为 '1'，可以有效地在字符串中创建一个新的活跃区段，或者以某种方式改变段的连接情况，从而增加活跃区段的总数。mx 记录了最大的可能增益。
4. 复杂度分析：
- • 时间复杂度：算法主要涉及一次遍历字符串 t（其长度为 n+2），过程中进行的都是常数时间的比较和加法操作。因此，时间复杂度为 O(n)。
- • 空间复杂度：算法只使用了几个额外的整数变量（如 mx, pre0, cnt, ans），不依赖于输入规模 n。因此，空间复杂度为 O(1)。

总结

该问题的解决方案通过一次遍历字符串，统计连续字符段，并重点关注相邻的 '0' 段，寻找最优操作机会。最终结果由初始活跃区段数加上相邻两段 '0' 的最大总长度得到。这种方法高效且直接，满足了题目对复杂度的要求。

总的时间复杂度为 O(n)，总的额外空间复杂度为 O(1)。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func maxActiveSectionsAfterTrade(s string) (ans int) {
    mx := 0
    pre0 := math.MinInt
    cnt := 0
    for i := rangelen(s) {
        cnt++
        if i == len(s)-1 || s[i] != s[i+1] { // i 是这一段的末尾
            if s[i] == '1' {
                ans += cnt
            } else {
                mx = max(mx, pre0+cnt)
                pre0 = cnt
            }
            cnt = 0
        }
    }
    return ans + mx
}
func main() {
    s := "01"
    result := maxActiveSectionsAfterTrade(s)
    fmt.Println(result)
}

Python完整代码如下：

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

def maxActiveSectionsAfterTrade(s: str) -> int:
    mx = 0
    pre0 = -10**9  # 使用一个很小的负数代替 math.MinInt
    cnt = 0
    n = len(s)
    ans = 0
    
    for i in range(n):
        cnt += 1
        # 检查是否是当前段的末尾：当前是最后一个字符，或者下一个字符不同
        if i == n - 1 or s[i] != s[i+1]:
            if s[i] == '1':
                ans += cnt
            else:
                mx = max(mx, pre0 + cnt)
                pre0 = cnt
            cnt = 0
    
    return ans + mx

def main():
    s = "01"
    result = maxActiveSectionsAfterTrade(s)
    print(result)

if __name__ == "__main__":
    main()