力扣-20. 有效的括号

看到类似：

括号匹配
嵌套结构
最近一个元素
撤销操作
后进先出

都应该想到：

栈

最后记得判断 stack.length。

function isValid(s: string): boolean {
  const stack: string[] = []

  const map: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{',
  }

  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char)
    } else {
      const top = stack.pop()

      if (top !== map[char]) {
        return false
      }
    }
  }

  return stack.length === 0
}

时间复杂度：O(n)，空间复杂度：O(n)。