leecode 32. 最长有效括号

本文主要是介绍leecode 32. 最长有效括号，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

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

示例 1:

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

示例 2:

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

解题思路：

preLen 数组记录的是当前字符匹配的有效括号子串的左侧下标；

例如： “（）（（）（））” 下标： “01234567”

解释： 下标为6的最小的有效括号子串左侧下标为5
有效括号子串 下标则为 3 ；
首先是分别计算出 最小的有效括号子串 下标位置信息；
然后合并相邻的 => 即为 有效括号子串 的下标信息；

下标为 2 的“（”，没有对应的有效括号子串，故下标为 2 ，即为自身的下标。

1）、首先是求出“)” 最近的“（”的位置，记录在preLen 数组里；
2）、合并相邻的 有效括号子串 修改preLen 数组的值；
3）、获取preLen 数组中最大的结果。

算法实现：


class Solution {
public:int longestValidParentheses(string s) {if (s.length() < 2)return 0 ;vector<int> ret ;int tmp ;vector<int> preLen(s.length(), 0) ;int maxLen = 0 ;/*第一步（**最小的有效括号子串**）和第二步（**有效括号子串**）下标计算*/for (int i = 0 ; i < s.length() ; i ++)//{preLen[i] = i ;if (ret.empty() || s[i] == '(')ret.push_back(i) ;else{tmp = ret.back() ;if (s[tmp] == '('){ret.pop_back() ;preLen[i] = tmp ;if (tmp == 0)continue ;if (preLen[tmp - 1] != (tmp - 1))preLen[i] = preLen[tmp - 1] ;}}}//for/*第三步，求整体最大*/for (int i = 0 ; i < s.length() ; i ++){if (i !=  preLen[i])maxLen = maxLen > (i + 1 - preLen[i]) ? maxLen : (i + 1 - preLen[i]) ;}return maxLen ;}
};