LeetCode刷题：有效括号与最小栈实现

在【Leetcode刷题笔记】中的"栈"部分，主要讨论的是LeetCode第20题——"有效的括号"（Valid Parentheses）。这是一道关于数据结构和算法的题目，考察了对栈（Stack）数据结构的理解和应用。问题的核心是判断给定的字符串，由圆括号、花括号和方括号组成，是否符合有效的括号匹配规则。 1. 题目背景： - 给定的字符串仅包含'('、')'、'{'、'}'和'['、']'这些字符。 - 有效的字符串应满足以下条件： - 所有左括号都有一个对应的相同类型的右括号，并且它们的配对是正确的。 - 左括号必须按照从左到右的顺序闭合。 - 空字符串视为有效。 2. 常规解法： - 使用栈来解决这个问题，因为栈是一种后进先出（LIFO）的数据结构，非常适合处理括号匹配。 - 初始化一个栈S。 - 遍历输入字符串中的每个字符： - 遇到开括号时，将其压入栈。 - 遇到闭括号时，检查栈顶元素是否与之匹配： - 匹配则弹出栈顶元素，继续遍历； - 不匹配则返回false，表示表达式无效。 - 遍历结束后，如果栈为空，说明所有括号都正确匹配，返回true；否则，表示还有未匹配的左括号，返回false。 3. 示例： - 示例1：输入 "()"，匹配成功，输出 true。 - 示例2：输入 "()[]{}", 匹配成功，输出 true。 - 示例3：输入 "(]", 由于没有匹配的左括号，输出 false。 - 示例4：输入 "([)]"，右括号 ] 未与左括号 () 匹配，输出 false。 - 示例5：输入 "{[]}", 匹配成功，输出 true。 4. 代码实现： - 作者使用Python定义了一个名为Stack的类，包含了基本的栈操作如 push（入栈）、pop（出栈）、peek（查看栈顶元素）、is_empty（判断栈是否为空）和size（获取栈大小）。 - 在Solution类中，isValid函数接收一个字符串s，通过调用Stack对象来判断括号是否有效。 总结起来，这个刷题笔记详细介绍了如何利用栈的特性解决有效的括号问题，包括栈的操作和逻辑实现，以及如何通过实际例子验证解决方案的正确性。这对于理解和应用栈在编程中的功能非常有帮助。