欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode---32. 最长有效括号---每日一题

程序员文章站 2022-07-12 23:17:26
...

32. 最长有效括号

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

示例 1:

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

示例 2:

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

思路

        左右各自遍历一次,不使用额外空间,空间复杂度为O(1),时间复杂度为O(n),有一个特别注意的点就是重置计数器,例如:从左到右遍历优先要’(’,若’(‘的数目还少于’)’,那么需要重置计数器为0。从右到左遍历也是一个道理。

实现代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size(), left = 0, right = 0, match = 0;
        // 从左到右遍历
        for(int i = 0; i < len; i++){
            if(s[i] == '(') ++left;
            else{
                ++right;
                if(left == right) match = max(match, left << 1);
                // 若右括号数目过多,不符合题意,重置计数器
                if(right > left) right = 0, left = 0;
            }
        }
        // 从右到左遍历,重置计数器
        left = 0, right = 0;
        for(int i = len - 1; i >= 0; i--){
            if(s[i] == ')') ++right;
            else{
                ++left;
                if(left == right) match = max(match, left << 1);
                // 与上面同理
                if(left > right) right = 0, left = 0;
            }
        }
        return match;
    }
};