题目描述
这是 力扣上的 856. 括号的分数:，难度为 中等。
题目分析
题目言简意赅，就是要我们按照给出的 3 种规则来计算输入的字符串中，括号的最终得分
- () 记 1 分
- ()() 记 2 分，即 1+1
- (()) 记 2 分，即 2*1
那么对于这三种情况，实际上就已经覆盖了输入字符串括号的所有组合，咱们仅仅是去一层一层的拨开洋葱的心而已
思考：
那么我们如何处理好上述三种情况的各种组合呢？
看到括号，我第一时间会想到使用栈的方式，但是咱们今天使用的栈并不是将括号入栈哦，而是我们要将目前的分数入栈，然后模拟这一个遍历括号的过程和计算分数的过程
我们输入的字符串的时候，我们自然是会遇到左括号(和右括号)，对于这俩我们需要不同情况不同对待
我们可以初始化一个存放 int 类型数据的栈，默认写一个 0 进去，表示当前得分为 0
- 左括号
(是一个括号的起始位置，当遍历输入字符串，遇到左括号(的时候，那么此时也还是不能得分的，因此我们可以向栈中追加一个 0 进去
那么，我们遍历的时候遇到右括号)的情况我们需要如何来处理呢？
- 当我们遇到右括号
)的时候，弹出当前元素的值，如果当前栈顶的元素的值是 0，那么很明显，当前右括号)的前一个元素必然是左括号(，这个时候咱们直接记 1 分就可以了，仅仅是说明本次的 右括号)已经配对了一个平衡括号()，我们是需要将这个值和当前的栈顶元素求和的
因为，当前情况还会存在 ()() 的情况，此时我们遍历到最后一个右括号的时候，最新的栈顶是 1 ，然后我们将当前的1 与栈顶求和， 即得到新的栈顶 2
- 对于遇到右括号
)，还剩下最后一个情况，那就是(())情况，我们是需要进行乘以 2 的
还是同样的道理，当我们遍历到最后一个右括号的时候，此时，我们是可以发现栈顶的值是 1 ，那么这个时候同理，我们将弹出栈顶元素，2*当前栈顶元素的结果 与 最新的栈的栈顶元素求和即可
那么，我们遇到右括号 ) 的时候，如何区分 是()() 还是 (())？
很简单，咱们遇到 ()() 的时候，遍历到最后一个右括号的时候，当前弹出的栈顶元素是 0，而 (()) 对应的是一个大于零的数
因此，咱们再和最新的栈进行求和的时候需要 max(2 * 之前栈顶的元素, 1)，这样说会不会更清晰了呢
接下来，咱们就可以来实现编码了，咱们这次使用 golang 的方式来进行实现
Golang 的实现方式：
func scoreOfParentheses(s string) int { // 使用栈的思想来进行实现 ans := []int{0} for _,c := range s { if c == '(' { // 遇到左括号的时候无脑向 ans 栈里面补零 ans = append(ans, 0) } else { // 遇到右括号的时候，此时需要注意是 )) 的情况，还是() 的情况， // 第 1 种 情况是前面的栈顶已经有大于 0 的值了 // 第 2 种 情况是，前面的栈顶肯定是 0，因此前面是 ( tmp := ans[len(ans) -1] ans = ans[:len(ans) -1] ans[len(ans) -1] += max(2*tmp, 1) } } return ans[0] } func max(a,b int) int { if a>b { return a } return b }
这种实现方式，咱们的时间复杂度是 O(n)，此处的 n 是表示输入字符串的长度 ，空间复杂度是O(n)，咱们引入了切片来模拟占空间
今天就到这里，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
