3499. 操作后最大活跃区段数 I

题目描述

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

'1' 表示一个活跃区段。
'0' 表示一个 非活跃 区段。

你可以执行 最多一次操作 来最大化 s 中的活跃区段数量。在一次操作中，你可以：

将一个被 '0' 包围的连续 '1' 区块转换为全 '0'。
然后，将一个被 '1' 包围的连续 '0' 区块转换为全 '1'。

返回在执行最优操作后，s 中的最大活跃区段数。

注意：处理时需要在 s 的两侧加上 '1' ，即 t = '1' + s + '1'。这些加上的 '1' 不会影响最终的计数。

示例 1：

输入： s = "01"

输出： 1

解释：

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

示例 2：

输入： s = "0100"

输出： 4

解释：

字符串 "0100" → 两端加上 '1' 后得到 "101001" 。
选择 "0100"，"101001" → "100001" → "111111" 。
最终的字符串去掉两端的 '1' 后为 "1111" 。最大活跃区段数为 4。

示例 3：

输入： s = "1000100"

输出： 7

解释：

字符串 "1000100" → 两端加上 '1' 后得到 "110001001" 。
选择 "000100"，"110001001" → "110000001" → "111111111"。
最终的字符串去掉两端的 '1' 后为 "1111111"。最大活跃区段数为 7。

示例 4：

输入： s = "01010"

输出： 4

解释：

字符串 "01010" → 两端加上 '1' 后得到 "1010101"。
选择 "010"，"1010101" → "1000101" → "1111101"。
最终的字符串去掉两端的 '1' 后为 "11110"。最大活跃区段数为 4。

提示：

1 <= n == s.length <= 10⁵
s[i] 仅包含 '0' 或 '1'

解法

方法一：贪心 + 双指针

题目实际上等价于求字符串 \(\textit{s}\) 中，字符 '1' 的数量，再加上相邻两个连续的字符 '0' 串中 `'0' 的最大数量。

因此，我们可以使用双指针来遍历字符串 \(\textit{s}\)，用一个变量 \(\textit{mx}\) 来记录相邻两个连续的字符 '0' 串中 '0' 的最大数量。我们还需要一个变量 \(\textit{pre}\) 来记录上一个连续的字符 '0' 串的数量。

每一次，我们统计当前连续相同字符的数量 \(\textit{cnt}\)，如果当前字符为 '1'，则将 \(\textit{cnt}\) 加入到答案中；如果当前字符为 '0'，则将 \(\textit{mx}\) 更新为 \(\textit{mx} = \max(\textit{mx}, \textit{pre} + \textit{cnt})\)，并将 \(\textit{pre}\) 更新为 \(\textit{cnt}\)。最后，我们将答案加上 \(\textit{mx}\) 即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串 \(\textit{s}\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        n = len(s)
        ans = i = 0
        pre, mx = -inf, 0
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            cur = j - i
            if s[i] == "1":
                ans += cur
            else:
                mx = max(mx, pre + cur)
                pre = cur
            i = j
        ans += mx
        return ans

class Solution {
    public int maxActiveSectionsAfterTrade(String s) {
        int n = s.length();
        int ans = 0, i = 0;
        int pre = Integer.MIN_VALUE, mx = 0;

        while (i < n) {
            int j = i + 1;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            int cur = j - i;
            if (s.charAt(i) == '1') {
                ans += cur;
            } else {
                mx = Math.max(mx, pre + cur);
                pre = cur;
            }
            i = j;
        }

        ans += mx;
        return ans;
    }
}

class Solution {
public:
    int maxActiveSectionsAfterTrade(std::string s) {
        int n = s.length();
        int ans = 0, i = 0;
        int pre = INT_MIN, mx = 0;

        while (i < n) {
            int j = i + 1;
            while (j < n && s[j] == s[i]) {
                j++;
            }
            int cur = j - i;
            if (s[i] == '1') {
                ans += cur;
            } else {
                mx = std::max(mx, pre + cur);
                pre = cur;
            }
            i = j;
        }

        ans += mx;
        return ans;
    }
};

func maxActiveSectionsAfterTrade(s string) (ans int) {
    n := len(s)
    pre, mx := math.MinInt, 0

    for i := 0; i < n; {
        j := i + 1
        for j < n && s[j] == s[i] {
            j++
        }
        cur := j - i
        if s[i] == '1' {
            ans += cur
        } else {
            mx = max(mx, pre+cur)
            pre = cur
        }
        i = j
    }

    ans += mx
    return
}

function maxActiveSectionsAfterTrade(s: string): number {
    let n = s.length;
    let [ans, mx] = [0, 0];
    let pre = Number.MIN_SAFE_INTEGER;

    for (let i = 0; i < n; ) {
        let j = i + 1;
        while (j < n && s[j] === s[i]) {
            j++;
        }
        let cur = j - i;
        if (s[i] === '1') {
            ans += cur;
        } else {
            mx = Math.max(mx, pre + cur);
            pre = cur;
        }
        i = j;
    }

    ans += mx;
    return ans;
}

3499. 操作后最大活跃区段数 I

题目描述

解法

方法一：贪心 + 双指针

评论