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;
const prefixOnes = new Int32Array(n + 1);
for (let i = 0; i < n; i++) {
prefixOnes[i + 1] = prefixOnes[i] + (s[i] === '1' ? 1 : 0);
}
const runs = [];
let i = 0;
while (i < n) {
const start = i;
while (i + 1 < n && s[i + 1] === s[start]) i++;
runs.push([s[start], start, i]);
i++;
}
const candidates = [];
for (let run = 1; run + 1 < runs.length; run++) {
if (runs[run][0] === '1' &&
runs[run - 1][0] === '0' && runs[run + 1][0] === '0') {
candidates.push({
left: runs[run - 1][1],
middleStart: runs[run][1],
middleEnd: runs[run][2],
right: runs[run + 1][2],
gain: runs[run - 1][2] - runs[run - 1][1] + 1 +
runs[run + 1][2] - runs[run + 1][1] + 1
});
}
}
let size = 1;
while (size < candidates.length) size <<= 1;
const tree = new Int32Array(size * 2);
for (let index = 0; index < candidates.length; index++) {
tree[size + index] = candidates[index].gain;
}
for (let index = size - 1; index > 0; index--) {
tree[index] = Math.max(tree[index * 2], tree[index * 2 + 1]);
}
const leftStarts = candidates.map(candidate => candidate.left);
const rightEnds = candidates.map(candidate => candidate.right);
const lowerBound = (values, target) => {
let low = 0, high = values.length;
while (low < high) {
const middle = (low + high) >> 1;
if (values[middle] < target) low = middle + 1;
else high = middle;
}
return low;
};
const upperBound = (values, target) => {
let low = 0, high = values.length;
while (low < high) {
const middle = (low + high) >> 1;
if (values[middle] <= target) low = middle + 1;
else high = middle;
}
return low;
};
const rangeMaximum = (left, right) => {
let result = 0;
for (left += size, right += size; left <= right; left >>= 1, right >>= 1) {
if (left & 1) result = Math.max(result, tree[left++]);
if (!(right & 1)) result = Math.max(result, tree[right--]);
}
return result;
};
return queries.map(([queryLeft, queryRight]) => {
const originalOnes = prefixOnes[queryRight + 1] - prefixOnes[queryLeft];
if (candidates.length === 0) return originalOnes;
const firstFull = lowerBound(leftStarts, queryLeft);
const lastFull = upperBound(rightEnds, queryRight) - 1;
let bestGain = firstFull <= lastFull
? rangeMaximum(firstFull, lastFull)
: 0;
const boundaryIndices = new Set([
firstFull - 1,
firstFull,
lastFull,
lastFull + 1
]);
for (const index of boundaryIndices) {
if (index < 0 || index >= candidates.length) continue;
const candidate = candidates[index];
const leftLength = candidate.middleStart -
Math.max(candidate.left, queryLeft);
const rightLength = Math.min(candidate.right, queryRight) -
candidate.middleEnd;
if (leftLength > 0 && rightLength > 0) {
bestGain = Math.max(bestGain, leftLength + rightLength);
}
}
return originalOnes + bestGain;
});
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n + q*k)，其中 n 是字符串长度，q 是查询数量，k 是平均段数 |
| 空间复杂度 | O(n + k)，用于存储段信息和位置映射 |