对大佬 牛客0X0001号 ac的代码进行讲解：
https://www.nowcoder.com/discuss/715645?source_id=profile_create_nctrack&channel=-1
例如s = '(()))()'
n = len(s)
0：‘（’进入变-1， stk：[-1]
1: ‘（’进入变-1，stk：[-1, -1]
2: “）”进入，检查stk最后一位，如果最后一位为-1说明此‘）’需要跟-1代表的“（”匹配 stk：[-1, 2]
3: "("进入 ，stk: [-1, 2, -1]
4 : ")"进入，stk:[-1, 2, 2]
注意这一步：
此步骤为 检测stk后面是否有连续的两个正数，如果有，这两个正数应该“相碰”（相乘）， 因为两个正数挨着，说明这两个完整的括号部分挨着，因此必为相乘操作；
stk.size()-2 , stk.size()-1，就是后两位的idx， 相乘之后存在stk.size()-2的位置，因为最后一位需要被pop掉。
此时stk [-1, 4]
5: ")"进入， 由于最后一位不是‘-1’，说明这个右括号“）”肯定有前面未匹配的左括号“（”在等待。
规律：前面未匹配的左括号比为倒数第二位。因为后面可以匹配的正整数已经相互碰撞成了一个新的整数，所以stk最右侧最多只能连续存在一个正整数。如果不信可以自己试试。
因此执行此步骤：
stk[stk.size() - 2] = (1 + stk[stk.size() - 1]) % mod; stk.pop_back();
此时stk:[5]
6：“（”进入，stk:[5, -1]
7：")"进入，stk:[5, 2] 碰撞相乘 得到[10]
最后输出结果
全部评论
(1) 回帖