使用双端队列求解的两种方式 | Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

基本分析

根据题意，我们可以设计如下处理流程：

• 从前往后遍历字符串，将不是 ) 的字符串从「尾部」放入队列中
• 当遇到 ) 时，从队列「尾部」取出字符串，直到遇到 ( 为止，并对取出字符串进行翻转
• 将翻转完成后字符串重新从「尾部」放入队列
• 循环上述过程，直到原字符串全部出来完成
• 从队列「头部」开始取字符，得到最终的答案

可以发现，上述过程需要用到双端队列（或者栈，使用栈的话，需要在最后一步对取出字符串再进行一次翻转）。

在 Java 中，双端队列可以使用自带的 ArrayDeque， 也可以直接使用数组进行模拟。

语言自带双端队列

代码：

class Solution {
    public String reverseParentheses(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        Deque<Character> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == ')') {
                StringBuilder path = new StringBuilder();
                while (!d.isEmpty()) {
                    if (d.peekLast() != '(') {
                        path.append(d.pollLast());
                    } else {
                        d.pollLast();
                        for (int j = 0; j < path.length(); j++) {
                            d.addLast(path.charAt(j));
                        }
                        break;
                    }
                }
            } else {
                d.addLast(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!d.isEmpty()) sb.append(d.pollFirst());
        return sb.toString();
    }
}
复制代码

• 时间复杂度：每个 ( 字符只会进出队列一次；) 字符串都不会进出队列，也只会被扫描一次；分析的重点在于普通字符，可以发现每个普通字符进出队列的次数取决于其右边的 ) 的个数，最坏情况下每个字符右边全是右括号，因此复杂度可以当做 $O(n^2)$，但实际计算量必然取不满 $n^2$，将普通字符的重复弹出均摊到整个字符串处理过程，可以看作是每个字符串都被遍历常数次，复杂度为 $O(n)$
• 空间复杂度：$O(n)$

数组模拟双端队列

代码：

class Solution {
    char[] deque = new char[2009];
    int head = 0, tail = -1;
    char[] path = new char[2009];
    public String reverseParentheses(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == ')') {
                int idx = 0;
                while (tail >= head) {
                    if (deque[tail] == '(') {
                        tail--;
                        for (int j = 0; j < idx; j++) {
                            deque[++tail] = path[j];
                        }
                        break;
                    } else {
                        path[idx++] = deque[tail--];
                    }
                }
            } else {
                deque[++tail] = c;
            }
        }
        StringBuilder sb = new StringBuilder();
        while (tail >= head) sb.append(deque[head++]);
        return sb.toString();
    }
}
复制代码

• 时间复杂度：每个 ( 字符只会进出队列一次；) 字符串都不会进出队列，也只会被扫描一次；分析的重点在于普通字符，可以发现每个普通字符进出队列的次数取决于其右边的 ) 的个数，最坏情况下每个字符右边全是右括号，因此复杂度可以当做 $O(n^2)$，但实际计算量必然取不满 $n^2$，将普通字符的重复弹出均摊到整个字符串处理过程，可以看作是每个字符串都被遍历常数次，复杂度为 $O(n)$
• 空间复杂度：$O(n)$