[面试题] 部门解散赔偿N谈妥，HR突然说签过竞业：5年不能干同行，赔50万

刚刷到这事儿，HR 这波操作属实把人看乐了。

公司某个部门解散，本来跟员工谈好了 N 的赔偿，大家也准备签字走人。结果临门一脚，HR 突然补了一句：签过竞业协议的，五年内不能干同行，否则赔公司 50 万。

好家伙，工作直接干没了，还想顺手把未来五年的饭碗也砸掉。本来都快签字的员工听完集体翻脸：那别谈了，必须 N+1，不然就去仲裁。

HR 大概还觉得自己在帮公司省钱，结果一句话把谈好的事全搅黄了。本来花 N 就能送走的人，现在一个个开始研究劳动法，领导的脸估计都僵了。

今日面试题

反转每对括号间的子串，别急着在原字符串上硬改

输入：

(u(love)i)

输出：

iloveu

这道题表面上是反转字符串，真正麻烦的地方在于括号可以嵌套。

像下面这个：

a(bc(de)f)g

不能看到右括号就随便抓一个左括号来配。内层 (de) 必须先处理成 ed，外层再把 bcedf 整体反转。

这种执行顺序已经很明显：后遇到的左括号先与右括号配对。这里我不会在原字符串上做下标切割，Java 的字符串本身不可变，来回 substring、拼接，表面省了几行代码，实际会造出不少临时对象。括号层级一深，代码也容易绕进去。

直接用栈。

遍历字符串时，准备一个 StringBuilder 来保存当前这一层已经读到的内容。遇到普通字符直接追加。遇到左括号，把外层内容压栈，再新建一个 StringBuilder 开始收集括号里的字符。遇到右括号，说明当前层结束：先反转当前内容，再弹出上一层，把反转结果接回去。

拿 (u(love)i) 跑一遍。读到第一个 (，空字符串入栈。接着读到 u，当前层是 u。再读到 (，把 u 压栈，开始处理 love。遇到右括号，love 反转成 evol，和上一层的 u 拼起来，得到 uevol。继续读到 i，当前内容变成 uevoli。最后一个右括号到来，整体反转，得到 iloveu。

代码不用写得太花：

import java.util.ArrayDeque;
import java.util.Deque;

public class BracketTextReverser {

    public String reverseInsideBrackets(String text) {
        Deque<StringBuilder> outerLayers = new ArrayDeque<>();
        StringBuilder currentLayer = new StringBuilder();

        for (int index = 0; index < text.length(); index++) {
            char token = text.charAt(index);

            if (token == '(') {
                outerLayers.push(currentLayer);
                currentLayer = new StringBuilder();
                continue;
            }

            if (token == ')') {
                currentLayer.reverse();

                StringBuilder parentLayer = outerLayers.pop();
                parentLayer.append(currentLayer);
                currentLayer = parentLayer;
                continue;
            }

            currentLayer.append(token);
        }

        return currentLayer.toString();
    }

    public static void main(String[] args) {
        BracketTextReverser reverser = new BracketTextReverser();

        System.out.println(
                reverser.reverseInsideBrackets("(u(love)i)")
        );

        System.out.println(
                reverser.reverseInsideBrackets("a(bc(de)f)g")
        );
    }
}

第二个测试数据的执行结果是：

afdecbg

内层 de 先变成 ed，外层内容成为 bcedf，随后再反转成 fdecb，最后和两边的 a、g 拼接。

这里有个细节：左括号入栈时压进去的是当前外层的 StringBuilder 引用，不是字符串副本。右括号处理完后，直接在原来的构建器上追加，省掉一次没必要的转换。

空间复杂度是 O(n)，因为栈和各层字符串最多保存全部字符。

时间复杂度一般可以看作 O(n) 到 O(n²) 之间。普通输入基本就是线性扫描，但如果括号嵌套特别深，同一批字符可能被多次反转和搬动，最坏情况会退化。

这题的关键不在 reverse()，而在于先确认处理顺序。只要看到嵌套括号，且要求从内向外计算，栈基本就该先拿出来了。