找回密码
 立即注册
查看: 18|回复: 0

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

[复制链接]
  • 打卡等级:即来则安
  • 打卡总天数:17
  • 打卡月天数:1
  • 打卡总奖励:185
  • 最近打卡:2025-08-06 09:29:10

21

主题

8

回帖

1万

积分

VIP

积分
10208
发表于 2025-7-23 13:59:12 | 显示全部楼层 |阅读模式
一、问题描述
给定一个包含'('、')'、'['、']'、'{'、'}'的字符串,找出其中最长的有效括号子串的长度。有效括号子串需要满足括号正确匹配且连续。
二、算法核心思想
  • 的巧妙应用:使用栈记录未匹配括号的位置
  • 边界处理:初始时压入-1作为虚拟边界
  • 动态更新:每次匹配成功时计算当前有效长度

三、完整代码实现(带详细注释)
  1. #include <iostream>
  2. #include <stack>
  3. #include <vector>
  4. using namespace std;

  5. int longestValidParentheses(string s) {
  6. stack<int> st;
  7. st.push(-1); // 初始边界,用于计算长度
  8. int max_len = 0;

  9. // 遍历字符串中的每个字符
  10. for(int i = 0; i < s.size(); i++) {
  11. // 如果是左括号,压入栈中
  12. if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
  13. st.push(i);
  14. } else {
  15. // 如果是右括号且栈不为空
  16. if(!st.empty() && st.top() != -1) {
  17. char top_char = s[st.top()];
  18. // 检查括号是否匹配
  19. if((top_char == '(' && s[i] == ')') ||
  20. (top_char == '[' && s[i] == ']') ||
  21. (top_char == '{' && s[i] == '}')) {
  22. st.pop(); // 匹配成功,弹出左括号
  23. max_len = max(max_len, i - st.top()); // 更新**长度
  24. } else {
  25. st.push(i); // 不匹配,压入当前位置
  26. }
  27. } else {
  28. st.push(i); // 栈为空或只有虚拟边界,压入当前位置
  29. }
  30. }
  31. }
  32. return max_len;
  33. }

  34. int main() {
  35. string s;
  36. cin >> s;
  37. cout << longestValidParentheses(s) << endl;
  38. return 0;
  39. }
  40. 四、算法分步解析
复制代码


四、算法分步解析
  • 初始化栈

    • 压入-1作为虚拟边界,便于后续长度计算
    • 初始化max_len为0,记录**有效长度

  • 遍历处理

    • 遇到左括号:压入栈中
    • 遇到右括号:检查栈顶是否匹配
    • 匹配成功:弹出栈顶,计算当前有效长度
    • 匹配失败:压入当前位置作为新边界

  • 结果计算

    • 每次成功匹配后,i - st.top()即为当前有效长度
    • 使用max函数保持**长度

五、常见误区与调试技巧
  • 忘记初始化虚拟边界
  • 未正确处理不匹配情况
  • 长度计算错误
  • 栈空判断遗漏

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

来源:信奥自学之路
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

SEO网站 ( 冀ICP备2025113422号-2 )|网站地图

Powered by Discuz! X3.5

快速回复 返回顶部 返回列表