0020. 有效的括号【简单】

1. 📝 Description
2. 💻 题解.1 - 栈

⏰ TODO：本节的 gif 图看起来很不直观，重新制作。

1. 📝 Description

leetcode

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([])"
输出：true

提示：

1 <= s.length <= 10^4
s 仅由括号 '()[]{}' 组成

2. 💻 题解.1 - 栈

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  const len = s.length;
  if (len % 2 !== 0) {
    return false; // 如果长度是奇数，直接返回 false，因为有效的括号必须成对出现
  }
  const stack = [];
  for (let i = 0; i < len; i++) {
    const str = s[i];
    if (str === '(') {
      stack.push(')'); // 遇到左括号 (，将对应的右括号 ) 压入栈
    } else if (str === '[') {
      stack.push(']'); // 遇到左括号 [，将对应的右括号 ] 压入栈
    } else if (str === '{') {
      stack.push('}'); // 遇到左括号 {，将对应的右括号 } 压入栈
    } else {
      if (str !== stack.pop()) return false; // 遇到右括号，检查是否与栈顶元素匹配
    }
  }
  return stack.length === 0; // 最后检查栈是否为空，为空则所有括号都匹配
};

执行流程
- 先判断传入的字符数量
  - 单数 return false;
  - 双数继续后续操作
- 遍历传入的字符串，判断当前字符
  - 如果是左括号
    - 令对应的右括号入栈，push
  - 如果是右括号
    - 如果此时栈不为空，那么，pop 出栈，比较从栈中取出的字符是否和当前的右括号相同
      - 相同 -> 继续遍历
      - 不同 -> return false;
    - 如果此时栈为空，那么直接 return false;
- 遍历结束
  - 如果栈中还存在成员，那么直接 return false;
  - 如果栈为空，说明在遍历过程中，配对过程没有出现问题。直接 return true; 即可。
问：如何理解这道题中的入栈和出栈的含义？
- 入栈（Push）：
- 当遇到一个左括号（(, [, {）时，我们将对应的右括号（), ], }）压入栈中。
- 例如，如果当前字符是 (，我们就将 ) 压入栈中。这样做是为了在后续遇到右括号时，能够与栈顶的右括号进行匹配。
- 出栈（Pop）：
- 当遇到一个右括号时，我们从栈中弹出栈顶元素，并检查它是否与当前的右括号匹配。
- 如果匹配，说明这对括号是有效的，继续处理下一个字符。
- 如果不匹配，或者栈为空（意味着没有相应的左括号），则返回 false，表示括号无效。
比如示例 1 s = "()"
- 入栈
  - 第一次遍历，遇到了 ( 括号，将 ) 入栈，意味着下个位置如果出现了右括号的话，那么一定得是 ) 才算匹配。
- 出栈
  - 第二次遍历，遇到了 )，和之前入栈压入的 ) 匹配，那么说明此时的括号是有效的。
比如示例 4 s = "([])"
- 入栈
  - 第一次遍历，遇到了 ( 括号，将 ) 入栈，意味着下个位置如果出现了右括号的话，那么一定得是 ) 才算匹配。
  - 此时栈的状态 stack = [')']
- 入栈
  - 第二次遍历，遇到了 [ 括号，将 ] 入栈，意味着下个位置如果出现了右括号的话，那么一定得是 ] 才算匹配。
  - 此时上一步入栈的 ) 将等待当前压入的 ] 被取出后才会被拿来匹配，这是栈的特性 - 后进先出。
  - 此时栈的状态 stack = [')', ']']
- 出栈
  - 第三次遍历，遇到了 ]，和之前入栈压入的 ] 匹配，那么说明此时的括号是有效的。
  - 此时栈状态 stack = [')']
- 出栈
  - 第四次遍历，遇到了 )，和之前入栈压入的 ) 匹配，那么说明此时的括号是有效的。
  - 此时栈为空，说明所有括号都已经配对完毕，返回 true。
用自然语言很难描述清楚，若写不出来，最好还是画画图，理清思路再写代码。

0020. 有效的括号【简单】 ​

1. 📝 Description ​

2. 💻 题解.1 - 栈 ​

0020. 有效的括号【简单】

1. 📝 Description

2. 💻 题解.1 - 栈