有效括号(合集)

有效括号

• 有效括号

 bool isLeft(char ch) {
    if (ch == '(' || ch == '[' || ch == '{') return true;
    return false;
}

bool isValid(string s) {
    stack<char> st;

    for (int i = 0; i < s.size(); i++) {
        // 左括号直接入栈
        if (isLeft(s[i])) st.push(s[i]);
        else { // 右括号
            // 但是栈内没有左括号，直接失败
            if (st.empty()) return false;
            char left = st.top();
            // 左括号不匹配，失败
            if (s[i] == ')' && left != '(') return false;
            if (s[i] == ']' && left != '[') return false;
            if (s[i] == '}' && left != '{') return false;
            // 匹配成功，出栈
            st.pop();
        }
    }
    // 最终栈为空，说明匹配完成
    return st.empty();
}

最长有效括号

• 最长有效括号

int longestValidParentheses(string s) {
    stack<int> st;
    st.push(-1); // 初始化基准

    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            st.pop();
            if (st.empty()) { // 栈空了，需要设置新基准
                st.push(i);
            } else {
                ans = max(ans, i - st.top()); // 计算的是距离
            }
        }
    }
    return ans;
}