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

今日学习内容：1047. 删除字符串中的所有相邻重复项。
今日任务： 把1047解决。
题目链接：力扣1047
视频链接：https://www.bilibili.com/video/BV12a411P7mw

解题思路

直接用字符串模拟栈，不用原生 stack，更高效简洁。

1. 遍历字符串：依次读取字符串中的每一个字符。
2. 利用栈进行匹配：
   如果栈为空，或者当前字符与栈顶字符不相同，说明没有形成相邻重复项，将当前字符压入栈中。
   如果当前字符与栈顶字符相同，说明找到了一对相邻重复项，此时将栈顶字符弹出（相当于把这一对重复字符都删除了）。
3. 构造结果：遍历完成后，栈中剩下的字符就是最终的结果。

一、看题首要反应

删除相邻重复项，是栈的经典应用题。不用额外开栈，直接用字符串当栈用，末尾就是栈顶，相同就删除，不同就尾插。

二、代码实现

1.栈模拟解法

代码如下：

C++版本

classSolution{public:stringremoveDuplicates(string s){string res;for(charc:s){if(!res.empty()&&res.back()==c){res.pop_back();}else{res.push_back(c);}}returnres;}};

2.注意点

用 stack 容器的话，写法冗余、效率低。换思路：可以直接用字符串模拟栈。

原因是：

1. 本题不需要栈的复杂操作，字符串的 back()、pop_back() 完全可以替代栈顶、出栈。
2. 原生栈还要逆序拼接，容易写错顺序，字符串模拟栈直接就是正序结果。

改用字符串充当栈，直接遍历比对末尾字符，省去逆序拼接步骤。

今日心得

遇到相邻消除类题目，优先想到用字符串当栈，简洁又高效。
栈类题目不一定非要用 stack 容器，灵活用字符串、数组模拟栈，能简化代码、避开顺序反转的坑。

坚持每日一题，稳步提升算法能力，继续加油！