LeetCode算法解题：最长回文子串与单调栈应用

"这个资源主要涵盖了LeetCode中的算法问题，特别是关于字符串处理的题目，包括最长回文子串的Manacher算法和使用单调栈去除重复字母的解决方案。" 在LeetCode的十月挑战中，我们可以看到两个关键的算法知识点： ### 1. Manacher(马拉车)算法 - 最长回文子串 Manacher算法是一种用于查找给定字符串中最长回文子串的高效方法。传统的暴力解法时间复杂度为O(n^2)，而Manacher算法通过利用回文串的对称性将时间复杂度降低到了O(n)。在给出的Java代码中，我们看到以下步骤： - 首先，将原始字符串`s`两边添加特殊字符`#`，形成新的字符串`s1`，目的是为了处理奇数长度和偶数长度的回文子串。 - 初始化一个数组`d1`，用于存储以每个位置为中心的回文子串的半径。 - 使用两个变量`l`和`r`来维护当前已知的最右侧回文子串的左右边界。 - 通过迭代更新`d1`数组，同时更新最大回文子串的长度`ans`和其起始位置`rem`。 - 在每次迭代中，判断当前位置`i`是否在已知的回文子串范围内，如果是，则可以利用已有的信息快速扩大回文子串的半径。 - 如果更新后的回文子串半径超过了已知的最大回文子串，就更新`ans`和`rem`，并可能需要调整`l`和`r`的值。 - 最后，根据`rem`和`d1[rem]`从`s1`中提取出最长回文子串。 ### 2. 单调栈 - 去除重复字母 单调栈通常用于处理与单调性相关的序列问题。在这个问题中，目标是移除字符串中的重复字符，同时保持字典序最小。单调栈的应用步骤如下： - 初始化一个空栈，用于存储字符串中的字符。 - 遍历字符串`s`的每一个字符，如果栈为空或者当前字符不等于栈顶字符： - 将当前字符压入栈中。 - 否则，即当前字符与栈顶字符相同，需要弹出栈顶字符，直到栈顶字符不等于当前字符为止。 - 遍历结束后，栈中的字符就是去重后的字典序最小的字符串。 例如，在示例1中，输入`s="bcabc"`，单调栈会依次压入`b`, `c`, `a`, `b`，当再次遇到`c`时，由于栈顶的`c`被弹出，最终栈内保留`b`, `a`, `c`，形成去重后的字典序最小的字符串`abc`。 在示例2中，输入`s="cbacdcbc"`，单调栈会处理掉重复的`c`和`b`，最终得到`cbad`。 通过这两个算法，我们可以看到在LeetCode的字符串处理问题中，巧妙地利用数据结构和算法可以显著提高解决问题的效率。在实际编程和面试中，熟练掌握这些技巧对于解决类似问题至关重要。