Hard
题目描述
给定一个长度为 n 的二进制字符串 s，其中：
- ‘1’ 表示活跃区段
- ‘0’ 表示非活跃区段
你最多可以执行一次交换来最大化 s 中活跃区段的数量。在一次交换中，你需要：
- 将被 ‘0’ 包围的连续 ‘1’ 块转换为全部 ‘0’
- 然后，将被 ‘1’ 包围的连续 ‘0’ 块转换为全部 ‘1’
另外，给定一个二维数组 queries，其中 queries[i] = [li, ri] 表示子字符串 s[li…ri]。
对于每个查询，确定在对子字符串 s[li…ri] 执行最优交换后，s 中活跃区段的最大可能数量。
返回数组 answer，其中 answer[i] 是 queries[i] 的结果。
注意：
- 对于每个查询，将 s[li…ri] 视为在两端增强了 ‘1’，形成 t = ‘1’ + s[li…ri] + ‘1’。增强的 ‘1’ 不计入最终计数。
- 查询彼此独立。
示例 1：
输入：s = "01", queries = [[0,1]]
输出：[1]
示例 2：
输入：s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]
输出：[4,3,1,1]
提示：
- 1 <= n == s.length <= 10^5
- 1 <= queries.length <= 10^5
- s[i] 是 ‘0’ 或 ‘1’
- queries[i] = [li, ri]
- 0 <= li <= ri < n
解题思路
解题思路
这道题的核心是理解交换操作的本质：将被0包围的1块转换为0，然后将被1包围的0块转换为1。
关键观察：
- 交换操作实际上是将一个0块及其相邻的两个1块合并成一个更大的1块
- 需要预处理字符串，将连续的0和1分成段，并为每段分配ID
- 对于每个0段，计算如果将其转换为1后能获得的最大收益
算法步骤：
- 段分割：将字符串分成连续的0段和1段，记录每段的起始位置、结束位置和长度
- 收益计算：对于每个0段i，计算
ans[i] = len[i-1] + len[i] + len[i+1]，即将0段转换为1段后的总长度 - 查询处理：对于每个查询范围[l,r]，找到完全包含在该范围内的0段，计算最大收益
- 边界处理：需要特别处理查询范围的首尾段，确保0段完全被包含
优化技巧：
- 使用线段树或简单遍历进行范围最大值查询
- 预计算每个位置对应的段ID，便于快速定位
- 特殊处理边界情况，如没有可交换的0段时返回原始1的数量
时间复杂度主要由查询处理决定，每个查询需要O(段数)的时间来找到最优解。
代码实现
class Solution {
public:
vector<int> maxActiveSectionsAfterTrade(string s, vector<vector<int>>& queries) {
int n = s.length();
// 分段：将连续的0和1分成段
vector<int> segStart, segEnd, segLen;
vector<char> segType;
vector<int> posToSeg(n);
int i = 0;
while (i < n) {
int start = i;
char type = s[i];
while (i < n && s[i] == type) {
posToSeg[i] = segStart.size();
i++;
}
segStart.push_back(start);
segEnd.push_back(i - 1);
segLen.push_back(i - start);
segType.push_back(type);
}
int segCount = segStart.size();
vector<int> ans(segCount, 0);
// 计算每个0段的收益
for (int i = 0; i < segCount; i++) {
if (segType[i] == '0') {
int gain = segLen[i];
if (i > 0 && segType[i-1] == '1') gain += segLen[i-1];
if (i < segCount-1 && segType[i+1] == '1') gain += segLen[i+1];
ans[i] = gain;
}
}
vector<int> result;
for (auto& query : queries) {
int l = query[0], r = query[1];
int leftSeg = posToSeg[l];
int rightSeg = posToSeg[r];
int maxGain = 0;
int originalOnes = 0;
// 计算原始1的数量
for (int i = l; i <= r; i++) {
if (s[i] == '1') originalOnes++;
}
// 检查每个0段是否完全包含在查询范围内
for (int i = leftSeg; i <= rightSeg; i++) {
if (segType[i] == '0') {
// 检查0段是否完全在查询范围内
if (segStart[i] >= l && segEnd[i] <= r) {
// 检查相邻的1段是否也在范围内
bool canTrade = true;
int gain = segLen[i];
if (i > 0 && segType[i-1] == '1') {
if (segStart[i-1] >= l) gain += segLen[i-1];
else canTrade = false;
}
if (i < segCount-1 && segType[i+1] == '1') {
if (segEnd[i+1] <= r) gain += segLen[i+1];
else canTrade = false;
}
if (canTrade) {
maxGain = max(maxGain, gain);
}
}
}
}
result.push_back(max(originalOnes, maxGain));
}
return result;
}
};
class Solution:
def maxActiveSectionsAfterTrade(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
# 分段：将连续的0和1分成段
segments = []
pos_to_seg = [0] * n
i = 0
while i < n:
start = i
seg_type = s[i]
while i < n and s[i] == seg_type:
pos_to_seg[i] = len(segments)
i += 1
segments.append({
'type': seg_type,
'start': start,
'end': i - 1,
'length': i - start
})
seg_count = len(segments)
result = []
for l, r in queries:
left_seg = pos_to_seg[l]
right_seg = pos_to_seg[r]
max_gain = 0
original_ones = sum(1 for i in range(l, r + 1) if s[i] == '1')
# 检查每个0段是否可以进行交换
for i in range(left_seg, right_seg + 1):
seg = segments[i]
if seg['type'] == '0':
# 检查0段是否完全在查询范围内
if seg['start'] >= l and seg['end'] <= r:
gain = seg['length']
can_trade = True
# 检查左相邻的1段
if i > 0 and segments[i-1]['type'] == '1':
if segments[i-1]['start'] >= l:
gain += segments[i-1]['length']
else:
can_trade = False
# 检查右相邻的1段
if i < seg_count - 1 and segments[i+1]['type'] == '1':
if segments[i+1]['end'] <= r:
gain += segments[i+1]['length']
else:
can_trade = False
if can_trade:
max_gain = max(max_gain, gain)
result.append(max(original_ones, max_gain))
return result
public class IList<int> MaxActiveSectionsAfterTrade(string s, int[][] queries) {
int n = s.Length;
// 分段：将连续的0和1分成段
var segments = new List<(char type, int start, int end, int length)>();
var posToSeg = new int[n];
int i = 0;
while (i < n) {
int start = i;
char segType = s[i];
while (i < n && s[i] == segType) {
posToSeg[i] = segments.Count;
i++;
}
segments.Add((segType, start, i - 1, i - start));
}
int segCount = segments.Count;
var result = new List<int>();
foreach (var query in queries) {
int l = query[0], r = query[1];
int leftSeg = posToSeg[l];
int rightSeg = posToSeg[r];
int maxGain = 0;
int originalOnes = 0;
// 计算原始1的数量
for (int j = l; j <= r; j++) {
if (s[j] == '1') originalOnes++;
}
// 检查每个0段是否可以进行交换
for (int j = leftSeg; j <= rightSeg; j++) {
var seg = segments[j];
if (seg.type == '0') {
// 检查0段是否完全在查询范围内
if (seg.start >= l && seg.end <= r) {
int gain = seg.length;
bool canTrade = true;
// 检查左相邻的1段
if (j > 0 && segments[j-1].type == '1') {
if (segments[j-1].start >= l) {
gain += segments[j-1].length;
} else {
canTrade = false;
}
}
// 检查右相邻的1段
if (j < segCount - 1 && segments[j+1].type == '1') {
if (segments[j+1].end <= r) {
gain += segments[j+1].length;
} else {
canTrade = false;
}
}
if (canTrade) {
maxGain = Math.Max(maxGain, gain);
}
}
}
}
result.Add(Math.Max(originalOnes, maxGain));
}
return result;
}
var maxActiveSectionsAfterTrade = function(s, queries) {
const n = s.length;
// 分段：将连续的0和1分成段
const segments = [];
const posToSeg = new Array(n);
let i = 0;
while (i < n) {
const start = i;
const segType = s[i];
while (i < n && s[i]
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n + q*k)，其中 n 是字符串长度，q 是查询数量，k 是平均段数 |
| 空间复杂度 | O(n + k)，用于存储段信息和位置映射 |