题解 | 最长有效括号

题干分析:

题目要求我们针对一个只含有'('和')'字符的字符串中选取最长的可匹配的括号字串,返回子串的长度.

首先关于括号匹配,由于匹配的括号一定为一对,因此我们可以确定这个返回值是个偶数(虽然基本没啥用)

算法思路:

我们有至少两个思路.

方法一便是直接模拟,我们创建一个既能存储整数,又能存储字符的栈(可以使用结构体),我们扫描整个字符串,

遇到'('便压栈,

遇到')':

首先判断栈顶是否为'(',

如果是,则匹配成功,将栈顶元素弹出,创建一个整数2表示已匹配字符串长度,然后持续弹出栈顶为数字的元素并相加,直到栈顶再次为字符,保证整数合并;

如果栈顶不是'('但是是数字,我们弹出该数字暂存,然后判断下一个字符是否为'(',

如果是则匹配成功,暂存数字+2,之后持续合并数字后压栈,

如果不是,暂存数字压栈,字符')'也压栈;

同时其他情况(栈顶为')')也直接压栈.

最后持续弹栈记录栈中最大的整数即为可匹配的最长括号字串.

方法二则更加巧妙:

我们已知符合要求的字串一定是'('的数量=')'的数量,我们假设从左侧开始扫描字符串并持续分别记录两种字符串的数量,当我们一旦发现两种字符数量相等便记录一下最大值.但我们也得注意,从左侧开始扫描只有"()"是合法的匹配方式,换句话说")("是不视为匹配发生的,因此扫描过程中但凡发现')'的数量多于'('的数量,证明无法匹配,两者均归零,此时开始就是下一个能够匹配的字串长度了.

同时我们还得注意,此方法到此为止并不能判断'('的数量多于')'时的情况,我们将上述从左到右扫描的方式反过来,再次进行扫描记录便能解决这个问题,虽然这样做会做些许重复工作,但最终结果是正确的.

实现代码:

struct CI {
        int i; // 整数表示已匹配成功的括号组
        char c;
        bool isInt;

        explicit CI(const int _i) : i(_i), c(0), isInt(true) {
        }

        explicit CI(const char _c) : i(0), c(_c), isInt(false) {
        }
    };

int longestValidParentheses(string s) {
        stack<CI> st;
        for (auto c: s) {
            // '('直接压栈
            if (c == '(') st.emplace(c);
            else {
                // ')'且栈顶为'('
                if (!st.empty() && st.top().c == '(') {
                    st.pop();
                    CI tmp(2);
                    // 持续合并整数
                    while (!st.empty() && st.top().isInt) {
                        tmp.i += st.top().i;
                        st.pop();
                    }
                    // 压入整数
                    st.push(tmp);
                } else if (!st.empty() && st.top().isInt) {
                    // ')'且栈顶为整数
                    CI tmp = st.top();
                    st.pop();
                    // 栈顶元素为'('
                    if (!st.empty() && st.top().c == '(') {
                        st.pop();
                        tmp.i += 2;
                        // 持续合并整数
                        while (!st.empty() && st.top().isInt) {
                            tmp.i += st.top().i;
                            st.pop();
                        }
                        st.push(tmp);
                    } else {
                        st.push(tmp);
                        st.emplace(c);
                    }
                } else st.emplace(c);
            }
        }
        int _max = 0;
        while (!st.empty()) {
            if (st.top().isInt) _max = max(_max, st.top().i);
            st.pop();
        }
        return _max;
    }

int longestValidParentheses(string s) {
        int maxLen = 0, left = 0, right = 0;
        const int n = s.length();

        // 从左到右：统计左右括号数量
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') left++;
            else right++;

            if (left == right) maxLen = max(maxLen, 2 * left);
            else if (right > left) left = right = 0; // 无效，重置
        }

        // 从右到左：处理左括号多余情况
        left = right = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == '(') left++;
            else right++;

            if (left == right) maxLen = max(maxLen, 2 * left);
            else if (left > right) left = right = 0; // 无效，重置
        }

        return maxLen;
    }

复杂度分析:

针对方法一:

每个元素最多进出栈一次,辅助判断的整数消耗的也是常量级别的时间与空间,因此时间复杂度与空间复杂度均为O(n).

针对方法二:

需要对字符串进行两次扫描,对每个字符进行操作只需要常数的时间,因此时间复杂度为O(n).

全过程只使用到了常数的额外空间,因此空间复杂度为O(1).