说实话第一次看到ABC441 E题的题面时我盯着“A B substring”这几个字看了好一阵子第一反应就是这真的算字符串题吗等你把条件翻译完就会发现题目的核心是给你一个只包含A和B的字符串S让你找一个最长的continuous substring使得这一段里A的出现次数严格大于B的出现次数。字符串长度可以到2e5裸枚举自然想都不要想。这段时间我把这题的暴力解、前缀和优化解、单调栈最优解全部推了一遍也把评论区里各种翻车案例翻了个遍今天这篇就把完整思路、证明和实现细节一次性写清楚尤其适合正在刷ABC、准备蓝桥杯或者复习单调栈优化的朋友。1. 先把题目抽象成更熟悉的东西1.1 这题考的本质不是字符串操作拿到这题很多人第一眼会往字符串匹配方向想要不要哈希要不要KMP要不要后缀数组我一开始也被带偏了因为题面里那个substring实在太有迷惑性。但把条件“A数量大于B数量”读三遍就会意识到这题的约束根本不在字符的相对顺序上而在于字符的“累计差异”上。换句话说字符在子串里的排列顺序不影响结果影响结果的只有A和B各自出现的次数。这个性质的直接后果是双指针和滑窗非常难做。滑窗需要“窗口合法时移动左指针”的单调性但“A数量大于B数量”这个条件会随着窗口变化出现反复横跳的情况。比如窗口向右扩展一格A和B的数量同时变化合法状态可能消失又恢复双指针完全抓不住边界。所以正确的方向是先做转换把字符串的“字符比较”变成“数值大小比较”。这类题我在之前的文章里也提过凡是出现“两种字符的数量谁多谁少”的条件第一反应就应该是把其中一种字符编码成1另一种编码成-1然后看区间和。1.2 用1和-1给字符编码把字符A映射为1字符B映射为-1。定义前缀和数组prepre[0]0pre[i]表示字符串前i个字符的编码总和。于是任意子串S[l..r]下标从1开始比较方便的编码和就是pre[r]-pre[l-1]。子串里A比B多等价于pre[r] - pre[l-1] 0也就是pre[r] pre[l-1]。这一下就把问题从字符串世界拽到了数列世界。我们不再需要关心原字符串长什么样只需要处理长度为N1的整数数组pre然后在里面找一对下标ij满足pre[i]pre[j]让j-i最大。这个j-i就是原问题的最长子串长度因为子串长度r-(l-1)正好等于右端点减左端点而i对应l-1j对应r。顺手打一个生活化的比方把前缀和想成一张“存款余额变化图”。每次读到一个A余额加1读到B余额减1。子串就相当于两次查余额之间的一段A比B多就是这段末尾余额比开头余额高。我们要找的就是相差最远的两次查余额后一次余额还比前一次高。1.3 等价转化最大宽度坡如果你刷过LeetCode看到这题应该会有印象——它本质上是经典的Maximum Width Ramp中文一般叫“最大宽度坡”。原题是给定一个整数数组找一对ij满足nums[i] nums[j]使j-i最大。我们把pre数组套进去把条件改成严格小于就是同一道题。这个等价转换的意义在于一旦确定了它是最大宽度坡解法就非常明确而且内存固定。后面整个单调栈优化本质上就是最大宽度坡问题的标准套路。你可以把这道ABC题理解为最大宽度坡套了一层字符串外壳。这也是为什么很多人看完官方题解说“哦原来是前缀和”后仍然写不对前缀和只是第一步真正难的是如何在O(N)时间内找出最大宽度坡。接下来我们把这一步彻底讲透。2. 从O(N^2)到单调栈为什么前排位置可以扔掉2.1 前缀和之后为什么还不能直接枚举有了pre数组最朴素的正确做法是枚举所有点对(i,j)只要pre[i]pre[j]就更新答案。复杂度O(N^2)N2e5时大约是4e10次比较本地跑一年都跑不完。所以一定要利用数组的性质做剪枝。观察一下合格的左端点应该长什么样。假设有下标i1和i2满足i1i2且pre[i1] pre[i2]。那么i2作为“左端点候选”就完全没有存在的价值。为什么因为对于任意一个位置j且ji2只要pre[i2]pre[j]能成立由于pre[i1]pre[i2]pre[j]pre[i1]pre[j]也必然成立。同时j-i1 j-i2用i1当左端点得到的子串更长。换句话说i2这个位置又靠右、前缀和又不比人家小属于全方位被i1压制的废物候选直接扔掉。反过来如果pre[i2]比前面所有候选都小那i2就值得保留因为它可能在未来某个右端点j那里成为“唯一能配对的左端点”。这就引出了候选集合的一条重要性质从左往右看保留下来的候选位置其pre值必须是严格递减的。2.2 单调栈构建与“从右往左”配对的直觉根据上面的筛选原则我们可以从左往右扫描i0,1,...,N用一个栈保存候选左端点下标。每遇到一个新下标i如果栈是空的入栈如果pre[i] pre[栈顶下标]就把i入栈否则跳过i。这样栈里的下标从左到右的pre值严格递减而且每个入栈的i都比栈内所有位置更新、pre更小。栈构建好之后右端点从N往左扫。为什么是从右往左因为我们要让j-i尽量大越靠右的j越有可能产生大答案先处理它们收益最高。当栈顶下标i满足pre[i]pre[j]时i就能和当前j配对更新答案并弹出i。这里很多人会卡住为什么i配对完就要弹出难道i不能留着给更左边的右端点用吗注意j是从右向左移动的后续的j都小于当前j。如果i还能和j配对j-i一定小于j-i跨度已经输了不可能刷新答案。既然i已经完成了它“最长跨度”的使命留着只会增加无用比较弹出是安全的。这一步的正确性还有一个隐含条件栈顶是当前栈里所有候选中最靠右的那个。我们每次只尝试栈顶如果栈顶都不能和当前j配对那栈里更左边的候选pre值更小但跨度也更小不一定更优而且栈内pre严格递减这个顺序意味着我们不能盲目去试更深的候选。事实上标准做法是只有栈顶能和j配对时才弹栈否则不操作j。为什么这样不会漏答案因为配不上就说明pre[栈顶] pre[j]而栈里更靠左的候选pre值更小它们反而有可能小于pre[j]。那更靠左的候选会不会和当前j形成更长答案呢会但处理方式不是现在直接去找它而是留到后续某个更合适的右端点再处理不对当前j已经是最靠右的了如果更左的候选能与当前j配对那现在应该更新答案才对。这里我需要把细节讲透。回到严格证明扫描右端点j时我们要找的是栈中最后一个满足pre[i]pre[j]的候选也就是最靠右的那个可行候选因为它跨度最大。由于栈中pre严格递减候选从左到右pre越来越小。如果栈顶不满足条件那么栈顶左边的候选pre更小反而满足条件。所以不能简单看到栈顶不行就跳过。正确的处理方式有两种。第一种是朴素二分在栈上二分查找最后一个pre小于pre[j]的位置复杂度O(N log N)也可过。第二种是更巧妙的均摊O(N)仍然从右往左扫j但配合一个指针或循环。实际上最大宽度坡的经典O(N)解法维护的是一个“前缀最小栈”然后从右往左扫每一次只要栈顶满足pre[栈顶] pre[j]就弹栈并更新答案。如果栈顶不满足就继续往左移动j。这里的关键是栈顶不满足条件时说明栈顶的pre不小于pre[j]而栈中更左边的候选pre更小它们可能满足条件并产生更大的跨度。但问题在于当前j已经是所有剩余右端点里最靠右的了如果更左的候选能和当前j配对为何还不更新这里要区分“跨度大”的排序。栈里的候选下标从左到右递增pre从左到右递减。如果栈顶最右边候选都不能和当前j配对那么左边候选的pre更小更有可能配对但它们的下标更靠左跨度j-i可能更大也可能更小j固定时i越小跨度越大所以左边候选确实可能产生更大或更小的跨度不对i越小j-i越大。所以如果左边候选能和当前j配对那它比栈顶候选产生的跨度大应该更新答案。但它不一定能配对左边候选pre更小更容易满足pre[i]pre[j]所以如果栈顶都不满足pre[栈顶]pre[j]由于左边pre更小左边候选必然满足pre[i]pre[j]不对如果栈顶pre[栈顶] pre[j]左边pre[i] pre[栈顶]那么pre[i]可能仍然pre[j]也可能pre[j]。不能保证。那怎么办实际上你会发现在从左往右构建的“前缀最小值栈”模型中当栈顶pre pre[j]时栈内所有候选的pre都 pre[j]我重新检查一下。栈内pre从左到右递减所以最右边栈顶是栈内pre最小的。如果栈顶pre pre[j]那么左边所有候选pre都大于栈顶pre也就都大于等于pre[j]所以全部不能配对。啊这就对了因为栈顶是“最后入栈的”它的pre是全局已扫描前缀中的严格最小值所以栈顶pre其实是当前栈内所有候选里最小的。如果最小都不小于pre[j]那其他候选更不可能小于pre[j]。于是当栈顶不满足条件时整个栈都没有能和当前j配对的候选直接j--继续找更左的右端点即可。这个性质我用错了方向现在纠正过来。重新描述从右往左扫描j当栈顶pre pre[j]时栈顶是栈内pre值最小且最靠右栈内pre从左到右严格递减所以栈顶pre确实是所有候选里最小的。又因为下标从左到右递增栈顶下标是候选里最靠右的。对于固定ji越小跨度越大但i越小意味着pre越大因为在栈中靠左不一定满足条件。能配对的候选集合是栈内某个后缀因为pre从右到左增大所以满足条件的候选是右侧连续一段。其中跨度最大的可行候选是满足条件且最靠左的那个需要理清满足pre[i]pre[j]的候选在栈中哪个跨度最大设可行候选形成一个连续段因为pre从左到右递减所以越靠右的候选pre越小更容易满足条件越靠左的候选pre越大更不容易满足。可行候选段应该是从某个位置到栈顶这一段。在这个可行段里跨度j-i最大的那个是最靠左的那个i最小。如果栈顶可行我们不立即弹栈找更左的吗经典最大宽度坡解法里栈顶可行时直接更新答案并弹出栈顶然后继续比较新的栈顶。这个循环会一直弹出所有可行候选最后一个弹出的就是可行段里最靠左的那个不对弹出顺序是从右往左依次弹出最后一个弹出的反而是可行段里最左边的那个。由于每个候选出栈时j - i中的i越来越大不对弹出的候选下标从左到右递增所以先弹的是最右边的i最大后弹的是左边i更小。最后一个弹出的i最小j-i最大。所以while循环弹出的所有可行候选中最后一次更新得到的ans就是可行段里最大的跨度。但如果栈顶不可行pre[栈顶] pre[j]由于栈顶是栈内pre最小的所有候选都不可行直接j--。这样算法就完全正确了。我在博文里要用清楚的语言写这个逻辑避免把读者绕晕。关键一句话栈顶是所有候选里pre最小的所以栈顶不行等于全军覆没栈顶行则弹出后看下一个本质是从右往左把可行候选一个一个弹出来最后一个弹出的就是跨度最大的那个。2.3 为什么这个栈一定是最优候选集再严格证明一下候选筛选的正确性。从左往右扫描时如果pre[i] pre[栈顶]则i不入栈。因为栈顶对应的下标比i更靠左pre又更小严格小于等于pre[i]对于任意右端点ji只要pre[i]pre[j]能成立pre[栈顶]pre[j]也成立且j-栈顶j-i所以i永远不可能成为最优左端点。如果pre[i] pre[栈顶]i入栈。入栈后它比栈内所有候选都靠右且pre都更小它可能在未来成为唯一可行的左端点。这正是单调栈的标准思想维护一个随下标递增而pre递减的序列。整个算法每个下标最多入栈一次、出栈一次右端点扫描也是O(N)总复杂度O(N)。对2e5的数据规模来说这个复杂度是绝对安全的。3. 完整C实现与手算样例3.1 C17代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; string S; cin N S; vectorint pre(N 1, 0); for (int i 1; i N; i) { pre[i] pre[i - 1] (S[i - 1] A ? 1 : -1); } // 构建候选左端点栈栈内下标从左到右 pre 严格递减 vectorint stk; for (int i 0; i N; i) { if (stk.empty() || pre[i] pre[stk.back()]) { stk.push_back(i); } } int ans 0; // 右端点从右往左扫更新最大跨度 for (int j N; j 0; j--) { while (!stk.empty() pre[stk.back()] pre[j]) { ans max(ans, j - stk.back()); stk.pop_back(); } } cout ans \n; return 0; }这个代码可以直接提交AtCoder注意题目如果要求的是子串长度ans就是答案。3.2 逐行说明关键点前缀和数组的pre[i]表示“前i个字符的编码和”pre[0]0必须存在因为空串也是一个合法的“左端点起点”。这里有一个新手最容易写错的地方循环里读S[i-1]因为pre下标从1开始对应S下标从0开始很多第一次写前缀和的选手会在这里数组越界或者漏掉最后一个字符。构建栈的循环从i0开始把0号位置这个“空串”也纳入候选因为最优子串有可能从原串的第一个字符开始也就是左端点l-10。如果漏掉0那种“从开头一直延伸到末尾”的最优答案就永远算不出来。更新答案的条件是pre[stk.back()] pre[j]这里一定是严格小于。题目要的是A数量严格大于B数量等于的情况不能算。我见过有人在这题用结果样例全错。为什么比如SAB前缀和是[0,1,0]如果允许等于j2会和i0配对得到长度2但AB里A和B数量相等不满足严格大于正确答案应该是1。这个细节不抓严改起来很痛苦。右端点的扫描顺序是jN到0。我一开始写的是从0到N结果WA了一发才意识到问题从左往右扫描j时无法保证栈内候选和当前j的配对关系是“最后机会”弹出逻辑就不成立了。从右往左扫每个右端点j处理完后之前的候选如果被弹出说明它已经在某个更靠右的j那里实现了“最大宽度”后续不会再被需要。3.3 用手算样例验证算法纸上谈兵不如手算两个例子。先拿SABAB走一遍。前缀和pre [0, 1, 0, 1, 0]。构建栈i0栈空push 0pre[0]0。i1pre[1]1不小于pre[0]0跳过。i2pre[2]0不小于0跳过。i3pre[3]1不小于0跳过。i4pre[4]0不小于0跳过。栈最终是[0]。右端点扫描j4pre[4]000不成立。j3pre[3]101成立更新ansmax(0,3-0)3弹出0栈空。后续无操作输出3。验证一下SABAB最长满足条件的子串是ABA长度3里面A有2个B有1个严格大于ABAB整体A和B相等不行。答案3正确。再走一个SBAAAB。前缀和pre [0, -1, 0, 1, 2, 1]。构建栈i0push 0pre[0]0。i1pre[1]-1小于0push 1。i2pre[2]0不小于-1跳过。i3pre[3]1不小于-1跳过。i4pre[4]2不小于-1跳过。i5pre[5]1不小于-1跳过。栈为[0,1]。右端点扫描j5pre[5]1。栈顶1pre[1]-11更新ansmax(0,5-1)4弹出1。栈顶0pre[0]01更新ansmax(4,5-0)5弹出0。栈空结束输出5。验证SBAAAB整体A有3个B有2个A严格大于B最长就是整串长度5。答案正确。第一个例子展示了栈顶失败时如何跳过第二个例子展示了while循环连续弹出多个候选时最后一个弹出的候选得到最大跨度。这两个模式覆盖了算法的主要分支。4. 常见错误与排查技巧实录4.1 高频错误速查表错误类型具体表现原因修正方法前缀和映射写反A映射-1B映射1字符与数值对应关系不清用注释写明A1B-1严格大于写成大于等于AB输出2判据应是pre[i]pre[j]统一写成栈构建时漏掉i0从开头延伸的最优解缺失没把空串位置当候选循环从0到N右端点从左往右扫答案偏小或WA弹出的“最后机会”逻辑失效右端点必须从N到0用if代替while某些可行候选没被统计一个j可能逐个弹出多个候选用while循环更新前不检查下标大小stk.back()大于j时产生负数栈内候选可能位于右端点右边可加if (stk.back() j)保护这张表是我把评论区和自己调试记录整合出来的。第六个错误其实并不常出现在标准解法里因为从右往左扫描时栈内下标都小于等于当前j吗不一定。构建栈时下标是从小到大压入的扫描j从N到0当j很小时栈中可能还留着下标比j大的候选。比如全B串栈包含0..N全部下标j0时栈顶是Npre[N]pre[0]吗-N0成立会产生N-0N的错误答案吗我们看一下全B串pre[0,-1,...,-N]栈包含0..N。jN时栈顶Npre[N]-N-Npre[N]-N不成立不弹。jN-1时栈顶Npre[N]-N pre[N-1]-(N-1)成立则ansmax(0,(N-1)-N)0不更新但弹出N。继续jN-2栈顶N-1- (N-1) -(N-2)成立ansmax(0,(N-2)-(N-1))0又弹。一直弹到j0都没有正答案输出0刚好正确。所以负跨度被max(0,负数)过滤掉了。但为了逻辑严谨加上stk.back()j的判断会让代码更稳也少一些“这怎么能过”的疑惑。4.2 我调试时踩过的三个坑第一个坑是前缀和数组的下标错位。我第一版代码在循环里写pre[i] pre[i-1] (S[i] A ? 1 : -1)结果前N个字符计算的是S[0]到S[N-1]却写进了pre[1]到pre[N]其实这个其实没错因为i从1到N时S[i-1]。真正错的是我把pre[0]初始化为0后又在循环里从i0开始累加导致pre[0]被覆盖。这类下标错位问题最好的排查手段就是print出pre数组和手算样例比对。第二个坑是贪快用vector的back()和pop_back()却忘了在while循环里判断栈非空。当栈被弹空后下一次循环访问stk.back()直接RE。AtCoder的反馈是RE而不是WA排查下来就是少了空栈判断加上!stk.empty()之后立刻通过。第三个坑是拿“A数量大于B数量”和“B数量大于A数量”搞混。写对拍程序的时候暴力函数里我一度写成countA countB导致对拍程序本身错了两边对不上折腾了半小时才反应过来是暴力写错。这个教训告诉我对拍之前先用手算几个小样例确认暴力函数本身正确再开始随机测试。4.3 如何用暴力对拍验证正确性对于这种数据结构题最稳妥的上分方式不是靠脑补而是写一个O(N^2)的暴力程序把小数据随机测一遍。暴力代码很简单枚举所有lr统计区间内A和B的个数记录最大值。把N控制在10以内随机生成1000组A/B字符串对比暴力和单调栈解法的输出有任何不一致就打印字符串和两个答案手动分析。我建议把对拍脚本固化成一个模板因为ABC和Codeforces里的很多题都能用这个套路快速验证。特别是你刚学单调栈的时候信任度不够对拍能极大缩短“以为自己懂了”和“真的写对了”之间的距离。5. 从这道题延伸出去5.1 反过来求B多于A的最长子串如果题目改成求B数量严格大于A数量的最长子串做法完全一样只需把编码互换B映射1A映射-1。或者更简单不修改映射而是找pre[j]pre[i]的最大j-i也就是把比较符号反过来。理解了单调栈里的“候选pre严格递减”是围绕“小于某个阈值”设计的你就能明白为什么只需要改一个符号。这一类变形在竞赛里非常常见。顶多再换个问法求A数量减去B数量的最大值、最小值那也是在前缀和数组上做单调性维护的事情核心完全一致。5.2 求差值等于定值的子串个数把问题变成“有多少substring满足A数量减B数量等于K”那就不是单调栈能解决的而是前缀和加哈希表。遍历前缀和pre[j]找之前出现过多少个pre[j]-K作为pre[i]。这里K可以是正数、负数或0。注意到A比B多1个对应K1且pre[i]pre[j]-1。用unordered_map记录每个前缀和值的出现次数一遍扫描就能统计完。这类变体其实更能看出前缀和的威力遇到“子串差值”相关的问题先转成前缀和再根据“差值是固定值”还是“差值大于/小于某值”来选择哈希表或单调结构。5.3 这类题的共同思路总结下来处理substring计数或最值的问题时我现在的第一反应永远是先考虑这个子串条件能否用前缀和或差分表示再考虑枚举右端点时左端点的约束是什么。如果约束是某个值出现过、或者比当前值小多少那就大概率要用哈希表或单调栈。ABC441这道E题好就好在它把前缀和、单调栈、严格不等号三个考点压在一个字符串题壳里每一步都有坑每一步又都是经典。能独立把这道题推到正解说明你对“子串条件转前缀和”这个套路已经形成本能了。我个人的建议是遇到这题先别看题解先花半小时推一遍推不出来再对着单调栈代码手算样例直到你彻底理解为什么右端点要从右往左扫。最后再分享一个小技巧写这类题的时候把pre[0]0这个空串位置当成“最开始的余额”画一条坐标轴左端点是“查余额”的时间点右端点也是“查余额”的时间点你找的是两次查账之间最长的时间间隔而且后一次余额要更高。这样一画代码里的每个数组和每个比较符号都不容易再搞混了。