leetcode 32. 最长有效括号 （困难）

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例1：

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”

示例2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

示例 3：

输入：s = “”
输出：0

🧡 算法分析

此题方法之一是用栈

我们通过标记合法的括号，可以得出，每一段合法的括号在字符串出现的位置一定是连续且不相交的

做括号匹配的这题可以用栈存储相应的信息，算法过程为：

1. 用栈维护当前待匹配的左括号的位置，同时用 start 记录一个新的可能合法的子串的起始位置，初始设为0
2. 如果s[i] ==‘(’，那么把i进栈
3. 如果s[i] == ‘)’,那么弹出栈顶元素 （代表栈顶的左括号匹配到了右括号），出栈后：

• 如果栈为空，说明以当前右括号为右端点的合法括号序列的左端点为start，则更新答案 i - start + 1

• 如果栈不为空，说明以当前右括号为右端点的合法括号序列的左端点为栈顶元素的下一个元素，则更新答案i - st.top()

4、遇到右括号)且当前栈为空，则当前的 start 开始的子串不再可能为合法子串了，下一个合法子串的起始位置必定是当前遍历位置 i + 1 开始，更新 start = i + 1。

5、最后返回答案即可

💚 代码实现

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        
        int re = 0;
        for(int i = 0, start = 0; i < s.size(); i ++)
        {
            if(s[i] == '(') st.push(i);
            else
            {
                if(st.size())
                {
                    st.pop();
                    if(st.empty()) re = max(re, i - start + 1);
                    else re= max(re, i - st.top());  // 因为之前已经弹出来了一个元素 (st.top() + 1) - 1
                }
                else 
                   start = i + 1;  // 更新
            }
        }
        return re;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

执行结果：

💙 时间复杂度分析

其中字符串只遍历一次， 时间复杂度为O(n)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！