力扣1047删除字符串中的所有相邻重复项（java，栈解法）

Problem: 1047. 删除字符串中的所有相邻重复项

思路

最直观的思路就是比较当前字的字符和相邻（也包含删除后再相邻）的上一字符是否相同，若相同则想办法去除两相同的字符，而关键就在如何较为便捷的比较同时去除当前和相邻（也包含删除后再相邻）的上一个一样的字符。由此我们可以想到使用栈这一数据结构。

具体的：

我们将字符串遍历，若栈为空或者当前栈顶元素与当前的字符不匹配则把当前字符加入到栈，否则出栈

解题方法

1.利用java双端队列模拟栈（便于将后续剩余的元素直接取出转换成字符串。如果直接利用栈还会多一步将字符逆序的操作！！！）
2.遍历字符串，用一个变量记录当前字符，栈为空或者当前栈顶元素与当前的字符 不匹配则把当前字符加入到栈，否则出栈（在双端队列中在对尾操作）.
3.取出双端队列中剩余元素利用StringBuilder将其拼接并最终转换为字符串。

复杂度

• 时间复杂度:

添加时间复杂度, 示例： $O(n)$

• 空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

class Solution {
    //Time Complexity: O(N)
    //Space Complexity: O(N)
    public String removeDuplicates(String s) {
        //使用双端队列模拟栈
        Deque deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //如果栈顶元素和当前的字符不相同则入栈
            if (deque.isEmpty() || deque.peekLast() != c) {
                deque.addLast(c);
            } else {
                deque.pollLast();
            }
        }
        //将栈中剩余的元素取出来
        StringBuilder sb = new StringBuilder();
        while (!deque.isEmpty()) {
            sb.append(deque.pollFirst());
        }
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24