洛谷P10472题解：利用栈求解最长有效括号

一、题目解读

洛谷P10472题要求计算给定字符串中最长有效括号的长度。有效括号指括号成对匹配（如"()[]{}"），子串需连续且内部嵌套正确。题目核心在于判断括号匹配的连续性，并找出最长合法子串。该问题常见于算法练习，考验对栈结构的理解和字符串处理能力。

二、解题思路

采用栈（Stack）结构解决该问题。核心思想：遍历字符串，左括号入栈，右括号尝试与栈顶匹配。若匹配成功则弹出栈顶，更新最长长度；若不匹配或栈空，则将当前位置入栈作为新“分割点”。通过栈的压入与弹出动态维护匹配区间，最终得到最长有效子串长度。

三、解题步骤

1. 初始化：创建栈并压入-1作为初始边界（避免空栈时的计算问题）。

2. 遍历字符串：

    若为左括号（'('、'['、'{')，直接入栈记录位置；

    若为右括号，分情况处理：

        栈顶为对应左括号（如栈顶为'('且当前为')'），弹出栈顶并计算当前区间长度（i - 栈顶位置），更新max_len；

        不匹配或栈空时，将当前位置i入栈（标记无效区间的分割点）。

3. 结果返回：遍历结束后，max_len即为最长有效括号长度。

四、代码与注释

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int longestValidParentheses(string s) {
    stack<int> st;  
    st.push(-1); // 初始边界，避免空栈时i - st.top()出错  
    int max_len = 0;  
    
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '(' || s[i] == '[' || s[i] == '{') { // 左括号直接入栈  
            st.push(i);
        } else {  
            if(!st.empty() && st.top()!= -1) { // 栈非空且非边界  
                char top_char = s[st.top()];  
                if((top_char == '(' && s[i] == ')') ||  
                   (top_char == '[' && s[i] == ']') ||  
                   (top_char == '{' && s[i] == '}')) { // 匹配成功  
                    st.pop();  
                    max_len = max(max_len, i - st.top()); // 更新长度  
                } else { // 不匹配，当前位置作为新分割点  
                    st.push(i);
                }
            } else { // 栈空或边界，直接入栈  
                st.push(i);
            }
        }
    }
    return max_len;
}

int main() {
    string s;
    cin >> s;
    cout << longestValidParentheses(s) << endl;
    return 0;
}

注释说明：代码通过栈记录括号位置，利用边界标记和区间计算动态维护有效长度，关键逻辑集中在右括号处理分支，巧妙利用栈顶元素判断匹配状态。

五、总结

本解法利用栈的“后进先出”特性，将括号匹配问题转化为位置区间的动态划分。初始边界-1的设计避免了空栈时索引计算的异常，提升了代码鲁棒性。时间复杂度O(n)，空间复杂度O(n)（栈最大存储n个位置），适用于大多数场景。此外，可拓展至其他括号相关匹配问题，为算法学习提供典型范例。