个人评价：栈使用的典型场景，最近正好梳理到栈，其实还是蛮有趣的~

题目难度：🌟 （参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 ）

另，通常算法题会考察分析时间复杂度和空间复杂度，可参考笔者之前的文章

「数据结构&算法」必知必会系列：3. 时间 & 空间复杂度（下）

对栈不熟悉的，建议先参考阅读：「数据结构&算法」必知必会系列：8. 常见数据结构——栈

有效的括号

题目描述

20.有效的括号

给定一个只包括 ‘('，')'，'{'，'}'，'['，']’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([)]”

输出：false

示例 5：

输入：s = “{[]}”

输出：true

提示：

1 <= s.length <= 104 s 仅由括号 ‘()[]{}’ 组成

解题思路

栈的典型使用场景（此题其他方法笔者暂未研究）栈解题的思路如下：

  • 字符串的长度为奇数，我们可以直接返回 false，省去后续的遍历判断过程。
  • 栈保存未匹配的左括号。从左到右遍历字符串，为左括号，将其压入栈。
  • 当遍历至到右括号，如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串，并从栈顶取出一个匹配的左括号；否则，则返回 false。
  • 当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式，返回 true；否则，则返回 false。

Go 代码如下：

func isValid(s string) bool {
    sLen := len(s)
    if sLen%2 != 0 {
        return false
    }
    pairMap := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []byte{} // 初始化栈
    for i := 0; i < sLen; i++ { //遍历字符串
    if pairMap[s[i]] > 0 { //是否右括号
        if len(stack) == 0 || stack[len(stack)-1] != pairMap[s[i]] { //栈为空 或者 出栈不匹配
            return false
        }
        stack = stack[:len(stack)-1] //出栈
        } else { //左括号 =》入栈
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}

https://goplay.tools/snippet/cLjqRr1VTvL Go play~

复杂度？🙌 时间 O(n) 空间 O(n)

总结

栈的经典应用，此类需要用到 LIFO 后进先出思想的都可利用栈哦~

顺序栈（数组实现栈）的入栈push 和出栈pop方法也熟记一下（不就是append元素以及截取最后一个元素嘛）

stack = append(stack, input) //push
stack = stack[:len(stack)-1] //pop