首页 > 代码库 > Leetcode#32 Longest Valid Parentheses
Leetcode#32 Longest Valid Parentheses
原题地址
方法I：动态规划
len[i]表示从i开始到结束的最长合法括号串长度，则：
如果s[i] == "(" 且 s[i+len[i+1]+1]==")"，len[i] = len[i+1] + 2
否则len[i] = 0
方法II：辅助栈
跟那个直方图求最大面积有点类似，用一个栈保存合法括号串的长度，显然长度只能是大于0的偶数（废话），所以可以用0表示"("。
如果当前元素是"("，将0压栈
如果当前元素是")"，依次查看栈顶元素并弹栈
如果栈顶元素大于0，说明这是一个合法括号串的长度，那么累加到总长度上
如果栈顶元素等于0，说明遇到了一个"("，将总长度+2，然后重新压栈，如果有必要，更新最长括号长度
这样遍历完s以后，栈里面都是一些局部括号串的长度，以及一些0（代表未匹配的"("），然后再做一遍上面的操作即可
代码：（方法II）
1 int longestValidParentheses(string s) { 2 stack<int> st; 3 int len = 0; 4 int top = 0; 5 int maxLen = 0; 6 7 for (int i = 0; i < s.length(); i++) { 8 if (s[i] == ‘(‘) 9 st.push(0);10 else {11 len = 0;12 while (!st.empty()) {13 int top = st.top();14 st.pop();15 len += top;16 if (top == 0) {17 len += 2;18 st.push(len);19 break;20 }21 }22 maxLen = max(maxLen, len);23 }24 }25 26 len = 0;27 while (!st.empty()) {28 top = st.top();29 st.pop();30 if (top > 0)31 len += top;32 else {33 maxLen = max(maxLen, len);34 len = 0;35 }36 }37 maxLen = max(maxLen, len);38 39 return maxLen;40 }
Leetcode#32 Longest Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。