力扣 20. 有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
方案一：利用 最近相关性，遍历字符串，将元素顺序入栈，如果遍历到右括号，就判断上个元素和当前元素是否能构成有效括号。
func isValid(s string) bool {
// s 长度是奇数，就不可能构成有效括号对
if len(s) % 2 == 1 {
return false
}
// 定义集合，保存有效括号对信息
pairs := map[int32]int32{
'}': '{',
')': '(',
']': '[',
}
// 定义栈
stk := make([]int32, 0, len(s))
// 遍历 s 每个元素
for _, x := range s {
// 判断当前是否是右括号
v, ok := pairs[x]
// 当前是左括号，将括号入栈
if !ok {
stk = append(stk, x)
continue
}
// 当前是右括号，但栈为空，即 s 前面部分没有对应左括号
// 或者此前入栈的括号和当前遍历到的右括号不匹配
if len(stk) == 0 || stk[len(stk) - 1] != v{
return false
}
// 此前入栈的括号和当前括号构成有效括号
// 将此前入栈的括号出栈
stk = stk[:len(stk) - 1]
}
return len(stk) == 0
}
- 时间复杂度：O(n)，因为需要遍历所有字符串中所有字符，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，因为使用了一个长度不超过 n 的栈辅助计算，所以空间复杂度为 O(n)。