首页 > 代码库 > 【LeetCode】Longest Valid Parentheses
【LeetCode】Longest Valid Parentheses
Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
括号匹配的常规思路就是用进出栈。
但是这题的关键在于“连续匹配”，因此计算“连续匹配”长度时，本质就是求不匹配的括号之间最大长度。
也就是求进栈但未出栈的括号下标之间的最大差值，注意边界值：第一个留在栈中的括号之前的连续匹配长度。
class Solution {public: int longestValidParentheses(string s) { int ret = 0; stack<int> stk; //store the indexes of unmatched parentheses for(int i = 0; i < s.size(); i ++) { if(s[i] == ‘(‘) //unmatch stk.push(i); else {//s[i] == ‘)‘ if(!stk.empty() && s[stk.top()] == ‘(‘) //match stk.pop(); else //unmatch stk.push(i); } } if(stk.empty()) //all match ret = s.size(); else {//check every unmatched pair of parentheses int start; int end = s.size()-1; while(!stk.empty()) { start = stk.top(); stk.pop(); ret = max(ret, end-start); end = start-1; } //from begin to the first unmatched parenthese ret = max(ret, end+1); } return ret; }};
【LeetCode】Longest Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。