算法训练营第十九天|1047. 删除字符串中的所有相邻重复项

题目链接https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/ 视频讲解https://www.bilibili.com/video/BV12a411P7mw4核心思路解析为什么用栈这道题要求反复删除字符串中相邻且相同的字符对直到无法删除为止。这个过程类似于“消消乐”。栈是解决此问题的完美数据结构原因正如您所说栈帮助我们记录了遍历到当前元素时前一个元素是什么。更具体地说当遍历字符串时我们将字符依次与栈顶元素即“前一个”可能被保留的元素比较。如果当前字符与栈顶字符相同说明它们相邻且重复触发“消除”操作将栈顶弹出。如果不相同则将当前字符压入栈它成为新的“前一个”元素供后续比较。遍历完成后栈中剩余的元素就是删除所有相邻重复项后的最终结果。这个过程模拟了我们手动消除的过程但效率更高只需遍历一次字符串。算法步骤初始化一个空栈在C中可以直接用string类型模拟栈便于直接生成结果字符串。遍历输入字符串s的每一个字符ch。核心操作如果栈不为空且当前字符ch等于栈顶字符则弹出栈顶字符消除这对相邻重复项。否则将当前字符ch压入栈中。返回结果遍历结束后栈中剩余的字符连接起来就是最终答案。复杂度分析时间复杂度O(n)其中 n 是字符串的长度。我们只需要遍历字符串一次每个字符的入栈和出栈操作都是 O(1)。空间复杂度O(n)在最坏情况下字符串没有相邻重复如”abcdef“栈需要存储所有字符。#include string using namespace std; class Solution { public: string removeDuplicates(string s) { string stk; // 使用string模拟栈便于直接返回结果 for (char ch : s) { // 如果栈不空且当前字符与栈顶字符相同 if (!stk.empty() ch stk.back()) { stk.pop_back(); // 消除相邻重复对 } else { stk.push_back(ch); // 否则字符入栈 } } return stk; // 栈中内容即为结果 } };