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

ftggdnt

一、问题描述

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

二、算法核心思想

• 栈的巧妙应用：使用栈记录未匹配括号的位置
• 边界处理：初始时压入-1作为虚拟边界
• 动态更新：每次匹配成功时计算当前有效长度
  
  

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

1. #include <iostream>
   
2. #include <stack>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. int longestValidParentheses(string s) {
   
7.     stack<int> st;
   
8.     st.push(-1); // 初始边界，用于计算长度
   
9.     int max_len = 0;
   
10.    
    
11.     // 遍历字符串中的每个字符
    
12.     for(int i = 0; i < s.size(); i++) {
    
13.         // 如果是左括号，压入栈中
    
14.         if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
    
15.             st.push(i);
    
16.         } else {
    
17.             // 如果是右括号且栈不为空
    
18.             if(!st.empty() && st.top() != -1) {
    
19.                 char top_char = s[st.top()];
    
20.                 // 检查括号是否匹配
    
21.                 if((top_char == '(' && s[i] == ')') ||
    
22.                    (top_char == '[' && s[i] == ']') ||
    
23.                    (top_char == '{' && s[i] == '}')) {
    
24.                     st.pop(); // 匹配成功，弹出左括号
    
25.                     max_len = max(max_len, i - st.top()); // 更新**长度
    
26.                 } else {
    
27.                     st.push(i); // 不匹配，压入当前位置
    
28.                 }
    
29.             } else {
    
30.                 st.push(i); // 栈为空或只有虚拟边界，压入当前位置
    
31.             }
    
32.         }
    
33.     }
    
34.     return max_len;
    
35. }
    
36. 
    
37. int main() {
    
38.     string s;
    
39.     cin >> s;
    
40.     cout << longestValidParentheses(s) << endl;
    
41.     return 0;
    
42. }
    
43. 四、算法分步解析

复制代码

四、算法分步解析

• 初始化栈：
  
  
  • 压入-1作为虚拟边界，便于后续长度计算
  • 初始化max_len为0，记录**有效长度
    
    
• 遍历处理：
  
  
  • 遇到左括号：压入栈中
  • 遇到右括号：检查栈顶是否匹配
  • 匹配成功：弹出栈顶，计算当前有效长度
  • 匹配失败：压入当前位置作为新边界
    
    
• 结果计算：
  
  
  • 每次成功匹配后，i - st.top()即为当前有效长度
  • 使用max函数保持**长度
    
    

五、常见误区与调试技巧

• 忘记初始化虚拟边界
• 未正确处理不匹配情况
• 长度计算错误
• 栈空判断遗漏
  
  

六、扩展思考

• 如何修改算法只处理小括号？
• 如果不使用栈，能否用动态规划解决？
• 如何统计所有有效括号子串而不仅是**长度？
• 如何扩展到多行文本的括号匹配？
  
  

来源：信奥自学之路