合成大星星：题解¶
解法比较¶
出题人解法用双向链表保存尚未归约的符号及已形成的星星块。从一端加入符号后，只检查这一端能否合成新块或合并相邻块，反复归约并更新历史最大值。内部已稳定的部分不受新插入影响；每个块只会创建和删除常数次，所以下文的局部归约证明与摊还分析同样适用于出题人解法。
Codex（GPT-6）采用的实现用双端队列替代手工链表，保留块的含义和归约顺序，减少指针连接与节点池管理。初始长度为 \(n\) 、操作数为 \(m\) 时，两者总时间和空间均为 \(O(n+m)\) .这是同一算法的容器替换，未比较实际运行速度。
思路¶
把一个合法且已经配对完成的非空片段压缩成一个中性块，用 N（Neutral）表示，同时保存它的实际长度。N 只是算法中的块类型标记，不是输入字符。未配对的左星壳 < 与右星壳 > 各保留为长度为 \(1\) 的块。星屑 * 自身也是一个长度为 \(1\) 的中性块。
在块序列中重复使用三种局部合并规则：
N N合并为一个中性块。< >合并为一个中性块。< N >合并为一个中性块。
合并后的长度为各块长度之和。由于新字符只从序列的一端加入，原来内部的块已经不能再合并；因此只需在被更新的一端反复检查这些规则。用双端队列保存块，记录曾出现的最大中性块长度。这个最大长度就是当前最长合法片段的长度。
正确性¶
三种规则都把合法片段合并为等价的中性块，且保留原长度。充分合并后，相邻中性块已合并，未被合并的星壳无法与相邻块组成合法片段。任意合法连续子串必然位于某个中性块中；否则它将跨过一个未配对星壳，与合并完成相矛盾。所以最长合法片段的长度等于最大中性块长度。
每次只在一端插入新块，内部已有的可合并关系没有改变。所有新出现的可合并关系都接触该端；连续进行局部合并后再次得到充分合并的块序列。因此维护的答案在初始构造和每次操作后都正确。
程序记录的是“曾出现的最大中性块长度”。这与当前答案相同：插入不会删掉原序列中的合法片段，而中性块被合并时只会进入一个更长的中性块。因此答案不会随操作减小；没有中性块时答案为 \(0\) .
复杂度¶
每个输入标记创建一个块，每次合并至少减少一个块；总合并次数为 \(O(n+m)\) . 因此总时间为 \(O(n+m)\) ，空间为 \(O(n+m)\) .