打个笔记 题目不难 感觉LeetCode中等标签比AcWing低了个档
至少用栈$O(n^2)$暴力没问题 拿StringBuilder模拟栈操作还能再快点
但是预处理括号$O(n)$的那个奇幻漂流属实把我秀到了
盗个图 侵删 「虫洞法」一个指针的奇幻漂流

原题链接
就是把括号内部的字符串反转 括号可嵌套

直接用栈没问题
挨个遍历 左括号和普通字符直接入栈
遇到右括号 就依次出栈直到栈顶为左括号 出栈的这些字符按出栈顺序链接自然也就是逆序的了
然后栈顶左括号出栈 把组合成的逆序串重新压入栈

遍历完字符串 栈中从栈底到栈顶 自然也就想要的结果
但是如果依次出栈 要注意连接顺序
直接接在后面 还需要一次整体反转
所以采用StringBuilder模拟栈的操作
最终返回sb.toString()

而且StringBuilder可以随机存取和切片
我们不需要挨个字符出栈 只需要从后往前找第一个左括号的位置 再把左括号以后的那段子串截出来单独反转 同样删除末尾左括号再连接逆序串

class Solution {
    public String reverseParentheses(String s) {
        StringBuilder sb = new StringBuilder(), temp;
        int end = 0;
        for (char ch : s.toCharArray()) {
            if (ch == ')') {
                end = sb.length() - 1;
                while (sb.charAt(end) != '(') end--;  // 找从后往前第一个左括号
                temp = new StringBuilder(sb.substring(end + 1, sb.length()));  // 切片
                temp.reverse();  // 反转
                sb.delete(end, sb.length());  // 移除左括号 和 已经截出的子串
                sb.append(temp);  // 连接逆序串
            } else sb.append(ch);  // 左括号和普通字符直接入栈
        }
        return sb.toString();
    }
}

预处理括号 $O(n)$
把图拉下来看

初始指针还是从左向右跑 规定指针每遇到一个非括号字符 就连接到StringBuilder末尾
如果指针遇到括号 就空降到配套的另一个括号上（遇到左括号就移到对应的右括号 遇到右括号就移到对应的左括号） 并且把移动方向置反 （di = -di）

直到指针移出数组范围 也就遍历结束了

怎么找某个括号配套的另一个括号呢
用栈实现括号匹配没问题 那就整个HashMap或者一个数组进行标记
栈内存的是左括号的数组索引 如果栈顶i 当遇到右括号（索引j）时 map[i] = j; map[j] = i;

class Solution {
    public String reverseParentheses(String s) {
        char[] chs = s.toCharArray();  // 原字符串
        int[] map = new int[chs.length];  // 映射数组
        ArrayDeque<Integer> ad = new ArrayDeque<>();  // 栈
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] == '(') ad.push(i);  // 左括号的索引直接入栈
            else if (chs[i] == ')') {  // 遇到右括号
                map[ad.peek()] = i;  // 两边都要绑定
                map[i] = ad.peek();
                ad.pop();  // 栈顶已经匹配到了 移除
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0, di = 1; i >= 0 && i < chs.length; i += di) {  // 其实括号必然配套 最后只需要判断 i<chs.length 就行了
            if (chs[i] == '(' || chs[i] == ')') {  // 遇到括号
                i = map[i];  // 指针空降到对应的另一个上
                di = -di;  // 方向置反
            } else sb.append(chs[i]);  // 非括号字符直接连接
        }

        return sb.toString();
    }
}