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

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; } };