描述

题目描述

给我们一个字符串里面只会包含$()()$这两种字符, 然后问我们可以构成的最大的正确子串, 就是严格满足左右括号相同

样例解释

样例输入:

"(()"

我们可以很容易发现, 只有$()()$这个是满足的, 长度为$22$

所以我们的样例输出就是

2

题解

解法一: 贪心

解题思路

首先我们可以很容易知道, 我们的最终的答案他一定是满足这么一个条件的

左括号数量与右括号数量是相同的

然后我们还可以知道, 从前向后看的话, 我们可以确定必须严格保证时刻左括号的数量时刻大于等于右括号数量

如果不满足, 就把左右指针同时清零

这样会有这么一组情况$(()(()$这样我们会发现, 我们时刻都没有左右括号相同的时候

那么我们再反向遍历一次这里注意反向遍历的时候, 我们会发现原来的$(()(()$变成了$)(()(($

这样的时候我们其实再判断的时候就是要注意了, 这里我们要严格保证右括号比左括号多

代码实现

class Solution {
    int l = 0, r = 0, res = 0;
   public:
    int longestValidParentheses(string s) {
        if (s.size() == 0 or s.size() == 1) return 0;
//         如果当前没有字符串，或者当前字符串的长度为1，那么我们无解
        for (auto &it : s) {
            if (it == '(') l++;
            if (it == ')') r++;
            if (l == r) res = max(res, l + r);
            else if (l < r) l = r = 0;
        }
//         从前往后判断我们的字符串
        reverse(s.begin(), s.end());
        l = r = 0;
        for (auto &it : s) {
            if (it == '(') l++;
            if (it == ')') r++;
            if (l == r) res = max(res, l + r);
            else if (l > r) l = r = 0;
        }
//         从后往前再扫描一次，保证我们的做法的正确性
        return res;
    }
};

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 我们只是遍历了一次, 所以时间复杂度为$O(n)O(n)$

空间复杂度: $O(1)O(1)$

理由如下: 因为我们未引入额外的变量空间

解法二

实现思路

我们用一个变量维护我们合法子串的起始位置, 然后如果是左括号直接把下标入栈, 如果是右括号弹出栈顶元素, 然后更新答案, 这里有两种情况, 如果栈空了, 那么我们可以说明是当前位置到我们的其实位置, 如果栈不空, 就是我们现在的到我们前一个左括号的位置

然后我们就可以进行一个匹配, 我们当前右括号下标是$22$, 然后我们把栈顶的$11$弹出, 我们$2-0==22\; -\; 0\; ==\; 2$

所以答案就是$22$

代码实现

class Solution {
    int res = 0, begin = 0;
    stack<int> st;
//     栈存储左括号的下标
//     res是我们最长串的长度，begin是我们的开始位置
   public:
    int longestValidParentheses(string s) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(i);
//             如果左括号，直接下标入栈
            else {
                if (st.size()) {
//                     这里考虑我们如果现在栈不空，两种情况
                    st.pop();
                    st.size() ? res = max(res, i - st.top()) : res = max(res, i - begin + 1);
                } else {
                    begin = i + 1;
//                     栈空了，那么我们当前就是不合法的，从下一位开始判断
                }
            }
        }
        return res;
    }
};

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 我们遍历一次字符串

空间复杂度: $O(n)O(n)$

理由如下: 最坏情况下, 我们会把整个字符串都入栈