Leetcode_32. 最长有效括号

【原题链接】

32. 最长有效括号

【题目描述】

给定一个只包含 '('')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

【代码】

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        int res = 0, start = -1;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '('){
                stk.push(i);
            }else{
                if(stk.size()){
                    stk.pop();
                    if(!stk.size()){
                        res = max(res, i - start);
                    }else{
                        res = max(res, i - stk.top());//必须要实时更新,eg")((()())("
                    }
                }else{
                    start = i;
                }
            }
        }
        return res;
    }
};

执行用时: 8 ms

内存消耗: 7.5 MB

【时间复杂度】

O(n)

【注意点】

  1. 其他解法:无

  2. 比较难的

  3. 解题思路:首先要分段,从左往右遍历,如果一个序列左括号小于右括号,则包含这段序列的有效子序列最多就这么长了;之后统计有效长度,采用栈存储左括号的id,每次遇到右括号弹出匹配的左括号并计算更新右括号到栈顶元素或者区间最左侧(不是它对应的那个左括号)的距离。

  4. 证明分段处理正确:

评论