Shouyu

Appearance

代码随想录 栈与队列：20. 有效的括号 ​

题目链接：https://leetcode.cn/problems/valid-parentheses/

文章讲解：https://programmercarl.com/0020.有效的括号.html

题目描述 ​

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

    有效字符串需满足：

    • 左括号必须用相同类型的右括号闭合。
    • 左括号必须以正确的顺序闭合。
    • 注意空字符串可被认为是有效字符串。

    示例 1:

    • 输入: "()"
    • 输出: true

    示例 2:

    • 输入: "()[]{}"
    • 输出: true

    示例 3:

    • 输入: "(]"
    • 输出: false

    示例 4:

    • 输入: "([)]"
    • 输出: false

    示例 5:

    • 输入: "{[]}"
    • 输出: true

思考 ​

元素匹配的题目很适合使用栈。这道题就是，有左边就要对应有右边，对匹配性进行操作。

3种无效的情况： 1.左括号多了 2.右括号多了 3.左右括号不匹配例如}{

需要注意的是向 )({} 像这种情况 也归于第3种，方向颠倒或者说右括号的前面没有左括号。

怎么操作呢？

for循环遍历字符串，判断遍历元素是左括号的话就往栈添加对应的右括号，如果是右括号的话就需要判断栈是否为空或者等不等于栈顶元素，如果为空或者不等于栈顶元素，则直接无效，对应了第3种无效情况 和第二种无效情况。

st.top() 方法必须是在其本身存在的情况下，也就是 st 不能为空的前提下使用，否则一定错误。 不能出现 if(st.top()) 这样的用法。

剪枝，如果长度为奇数，那么一定无法闭合。

三种不匹配的情况：

  1. 左括号太多了，右括号无法消耗完
  2. 左括号和右括号对应不上
  3. 右括号还有，左括号就已经没有了
压入闭括号进栈 ​
cpp
#include <string>
using namespace std;
#include <stack>
bool isValid(string s) {
    stack<int> st;
    if(s.size() %2 != 0 ) return false;
    for(int i = 0; i<s.size();i++){
        if (s[i] == '('){
            st.push(')');
        } else if(s[i] == '['){
            st.push(']');
        } else if (s[i] == '{'){
            st.push('}');
        } else if (st.empty() || s[i] != st.top()){ // empty 是处理第三种情况。s[i] != st.top() 是处理第二种情况。
            return false;
        } else {
            st.pop();
        }
    }
    return st.empty(); // 处理第一种情况
}
压入开括号进栈 ​
cpp
#include <string>
using namespace std;
#include <stack>
bool isValid_positive_consideration(string s) {
    stack<char> st; // 使用 char 类型的栈来存储开括号

    // 优化：奇数长度的字符串必然无效
    if (s.length() % 2 != 0) {
        return false;
    }

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            // 如果是开括号，直接压入栈中
            st.push(c);
        } else {
            // 如果是闭括号
            // 1. 检查栈是否为空，如果为空，则没有开括号与之匹配，无效
            if (st.empty()) {
                return false;
            }

            // 2. 获取栈顶的开括号
            char top_char = st.top();

            // 3. 判断当前闭括号是否与栈顶的开括号匹配
            if ((c == ')' && top_char == '(') ||
                (c == ']' && top_char == '[') ||
                (c == '}' && top_char == '{')) {
                // 匹配成功，将栈顶的开括号弹出
                st.pop();
            } else {
                // 不匹配，无效
                return false;
            }
        }
    }

    // 遍历完所有字符后，如果栈为空，则表示所有括号都正确匹配
    return st.empty();
}

时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符最多被压入和弹出栈一次。*

空间复杂度：O(n)，在最坏的情况下（例如，字符串 "((((("），栈的大小可以达到 n。*

启发 ​

当遇到需要匹配成对的元素，或者处理具有嵌套结构的问题时，栈往往优先选择。

长度为奇数时可以进行剪枝操作。