删除最外层的括号 图解题解

这道题到底在问什么

输入

s = "(()())(())"

输出

"()()()"

最优解：一步一步想明白

1. 3记住这句口诀：左括号深度大于 0 才输出再加一，右括号先减一还大于 0 才输出。后面每一帧都在套它。
2. 4开局：深度计数器 depth = 0，结果串为空。上面一排是要扫的括号串，下面这根栈每压入一个左括号就长高一层，栈高就是当前深度。指针从第 0 个字符开始往右走。
3. 5指针移到第 0 个字符，是一个左括号。先看现在的深度是 0，也就是栈里还没闭合的左括号有 0 个，再决定这个字符输不输出。
4. 6这个左括号进栈前深度是 0，它正是一个原语最外层那一层，按规矩跳过不输出，只让深度加一变成 1。
5. 7指针移到第 1 个字符，是一个左括号。先看现在的深度是 1，也就是栈里还没闭合的左括号有 1 个，再决定这个字符输不输出。
6. 8这个左括号进栈前深度是 1，已经大于 0，说明外面还套着括号，它是内层的，要输出。先把 ( 写进结果，再让深度加一变成 2。
7. 9指针移到第 2 个字符，是一个右括号。先看现在的深度是 2，也就是栈里还没闭合的左括号有 2 个，再决定这个字符输不输出。
8. 10右括号先让深度减一，现在是 1，还大于 0，说明它封的不是最外层，要输出。把 ) 写进结果。
9. 11指针移到第 3 个字符，是一个左括号。先看现在的深度是 1，也就是栈里还没闭合的左括号有 1 个，再决定这个字符输不输出。
10. 12这个左括号进栈前深度是 1，已经大于 0，说明外面还套着括号，它是内层的，要输出。先把 ( 写进结果，再让深度加一变成 2。
11. 13指针移到第 4 个字符，是一个右括号。先看现在的深度是 2，也就是栈里还没闭合的左括号有 2 个，再决定这个字符输不输出。
12. 14右括号先让深度减一，现在是 1，还大于 0，说明它封的不是最外层，要输出。把 ) 写进结果。
13. 15指针移到第 5 个字符，是一个右括号。先看现在的深度是 1，也就是栈里还没闭合的左括号有 1 个，再决定这个字符输不输出。
14. 16右括号让深度减一变成 0，正好闭合了一整个原语，它是最外层的右括号，跳过不输出，结果里又攒齐了一段。
15. 17指针移到第 6 个字符，是一个左括号。先看现在的深度是 0，也就是栈里还没闭合的左括号有 0 个，再决定这个字符输不输出。
16. 18这个左括号进栈前深度是 0，它正是一个原语最外层那一层，按规矩跳过不输出，只让深度加一变成 1。
17. 19指针移到第 7 个字符，是一个左括号。先看现在的深度是 1，也就是栈里还没闭合的左括号有 1 个，再决定这个字符输不输出。
18. 20这个左括号进栈前深度是 1，已经大于 0，说明外面还套着括号，它是内层的，要输出。先把 ( 写进结果，再让深度加一变成 2。
19. 21指针移到第 8 个字符，是一个右括号。先看现在的深度是 2，也就是栈里还没闭合的左括号有 2 个，再决定这个字符输不输出。
20. 22右括号先让深度减一，现在是 1，还大于 0，说明它封的不是最外层，要输出。把 ) 写进结果。
21. 23指针移到第 9 个字符，是一个右括号。先看现在的深度是 1，也就是栈里还没闭合的左括号有 1 个，再决定这个字符输不输出。
22. 24右括号让深度减一变成 0，正好闭合了一整个原语，它是最外层的右括号，跳过不输出，结果里又攒齐了一段。
23. 25整串扫完，栈又空了、深度从 0 出发也回到 0，说明括号配对完整。最外层的每一对括号都被跳过，留下的就是去掉外层后的结果 ()()()。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        ans = []
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
                if cnt > 1:
                    ans.append(c)
            else:
                cnt -= 1
                if cnt > 0:
                    ans.append(c)
        return ''.join(ans)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    string removeOuterParentheses(string s) {
        string ans;
        int cnt = 0;
        for (char& c : s) {
            if (c == '(') {
                if (++cnt > 1) {
                    ans.push_back(c);
                }
            } else {
                if (--cnt) {
                    ans.push_back(c);
                }
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder ans = new StringBuilder();
        int cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(') {
                if (++cnt > 1) {
                    ans.append(c);
                }
            } else {
                if (--cnt > 0) {
                    ans.append(c);
                }
            }
        }
        return ans.toString();
    }
}

复杂度

面试官可能追问