网络异常，图片无法展示
|
基本分析
根据题意，我们可以设计如下处理流程：
- 从前往后遍历字符串，将不是
)的字符串从「尾部」放入队列中 - 当遇到
)时，从队列「尾部」取出字符串，直到遇到(为止，并对取出字符串进行翻转 - 将翻转完成后字符串重新从「尾部」放入队列
- 循环上述过程，直到原字符串全部出来完成
- 从队列「头部」开始取字符，得到最终的答案
可以发现，上述过程需要用到双端队列（或者栈，使用栈的话，需要在最后一步对取出字符串再进行一次翻转）。
在 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)O(n2) - 空间复杂度：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)O(n2) - 空间复杂度：O(n)O(n)
