- 打卡等级:即来则安
- 打卡总天数:17
- 打卡月天数:1
- 打卡总奖励:185
- 最近打卡:2025-08-06 09:29:10
VIP
- 积分
- 10208
|
一、问题描述给定一个包含'('、')'、'['、']'、'{'、'}'的字符串,找出其中最长的有效括号子串的长度。有效括号子串需要满足括号正确匹配且连续。 二、算法核心思想边界处理:初始时压入-1作为虚拟边界 动态更新:每次匹配成功时计算当前有效长度
三、完整代码实现(带详细注释)
- #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作为虚拟边界,便于后续长度计算 初始化max_len为0,记录**有效长度
遍历处理:
遇到左括号:压入栈中 遇到右括号:检查栈顶是否匹配 匹配成功:弹出栈顶,计算当前有效长度 匹配失败:压入当前位置作为新边界
结果计算:
五、常见误区与调试技巧忘记初始化虚拟边界 未正确处理不匹配情况 长度计算错误 栈空判断遗漏
六、扩展思考如何修改算法只处理小括号? 如何统计所有有效括号子串而不仅是**长度?
来源:信奥自学之路
|
|