洛谷P10472题解：使用栈高效求解最长有效括号子串

一、问题描述

给定一个包含'('、')'、'['、']'、'{'、'}'的字符串，找出其中最长的有效括号子串的长度。有效括号子串需要满足括号正确匹配且连续。

二、算法核心思想

1. 栈的巧妙应用：使用栈记录未匹配括号的位置

2. 边界处理：初始时压入-1作为虚拟边界

3. 动态更新：每次匹配成功时计算当前有效长度

三、完整代码实现（带详细注释）

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

int longestValidParentheses(string s) {
    stack<int> st;
    st.push(-1); // 初始边界，用于计算长度
    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. 初始化栈：

• 压入-1作为虚拟边界，便于后续长度计算

• 初始化max_len为0，记录最大有效长度

2. 遍历处理：

• 遇到左括号：压入栈中

• 遇到右括号：检查栈顶是否匹配

• 匹配成功：弹出栈顶，计算当前有效长度

• 匹配失败：压入当前位置作为新边界

3. 结果计算：

• 每次成功匹配后，i - st.top()即为当前有效长度

• 使用max函数保持最大长度

五、常见误区与调试技巧

1. 忘记初始化虚拟边界

2. 未正确处理不匹配情况

3. 长度计算错误

4. 栈空判断遗漏

六、扩展思考

1. 如何修改算法只处理小括号？

2. 如果不使用栈，能否用动态规划解决？

3. 如何统计所有有效括号子串而不仅是最大长度？

4. 如何扩展到多行文本的括号匹配？