这道题是 LeetCode 3777题名为「使子字符串变交替的最少删除次数」(Minimum Deletions to Make Alternating Substring)。这是一道困难题需要同时处理动态修改和区间查询。 题目描述· 输入一个长度为 n 的字符串 s仅含 A/B和 q 个查询 queries。· 操作类型· [1, j]翻转 s[j]A变BB变A。· [2, l, r]查询将子串 s[l..r] 变为交替字符串相邻字符不同所需的最少删除次数。· 输出按顺序返回所有 [2, l, r] 查询的结果数组。 核心解法线段树 (Segment Tree)由于有高达 10^5 的单点更新和区间查询需要一种能同时高效处理这两种操作的数据结构——线段树。核心思路对于任何区间其最小删除次数可以分治合并。用线段树维护每个区间三个信息1. 左端点字符 (lc)2. 右端点字符 (rc)3. 最小删除次数 (del_cnt)合并方法合并左右子区间时总删除次数 左区间删除次数 右区间删除次数 左区间右端点 右区间左端点 ? 1 : 0。 参考代码 (Java)javaclass Solution {// 线段树节点static class Data {char lc, rc; // 区间左右端点字符int del; // 变成交替串的最小删除次数Data(char lc, char rc, int del) { this.lc lc; this.rc rc; this.del del; }}private Data[] tree;private char[] chars;public int[] minDeletions(String s, int[][] queries) {int n s.length();this.chars s.toCharArray();// 线段树数组大小开4倍nthis.tree new Data[4 * n];build(1, 0, n - 1);ListInteger ansList new ArrayList();for (int[] q : queries) {if (q[0] 1) { // 更新操作update(1, 0, n - 1, q[1]);} else { // 查询操作Data res query(1, 0, n - 1, q[1], q[2]);ansList.add(res.del);}}return ansList.stream().mapToInt(i - i).toArray();}// 合并两个节点信息private Data merge(Data left, Data right) {if (left null) return right;if (right null) return left;// 核心逻辑左右相邻字符相同则需多删一个int add (left.rc right.lc) ? 1 : 0;return new Data(left.lc, right.rc, left.del right.del add);}// 构建线段树private void build(int node, int l, int r) {if (l r) {tree[node] new Data(chars[l], chars[l], 0);return;}int mid (l r) / 2;build(node * 2, l, mid);build(node * 2 1, mid 1, r);tree[node] merge(tree[node * 2], tree[node * 2 1]);}// 单点更新翻转字符private void update(int node, int l, int r, int idx) {if (l r) {// 翻转字符A - Bchars[l] (chars[l] A) ? B : A;tree[node] new Data(chars[l], chars[l], 0);return;}int mid (l r) / 2;if (idx mid) update(node * 2, l, mid, idx);else update(node * 2 1, mid 1, r, idx);tree[node] merge(tree[node * 2], tree[node * 2 1]);}// 区间查询private Data query(int node, int l, int r, int ql, int qr) {if (ql l r qr) return tree[node];int mid (l r) / 2;if (qr mid) return query(node * 2, l, mid, ql, qr);if (ql mid) return query(node * 2 1, mid 1, r, ql, qr);// 查询区间跨越左右子树需要合并结果Data leftRes query(node * 2, l, mid, ql, qr);Data rightRes query(node * 2 1, mid 1, r, ql, qr);return merge(leftRes, rightRes);}}⏱️ 复杂度分析· 时间复杂度· 构建树O(n)· 每次更新或查询O(log n)· 总体O((n q) * log n)· 空间复杂度O(n)主要是线段树数组开销。理解“左右端点字符 删除次数”这个合并逻辑是关键。如果还有不清楚的地方随时可以再问我。