您当前位置：首页 > php开源 > php教程 > LeetCode:Longest Valid Parentheses

LeetCode:Longest Valid Parentheses

来源：程序员人生发布时间：2016-06-03 13:36:07 阅读次数：2093次

Longest Valid Parentheses

Total Accepted: 63715 Total Submissions: 282480 Difficulty: Hard

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.

Subscribe to see which companies asked this question

Hide Tags

Dynamic Programming String

Hide Similar Problems

(E) Valid Parentheses

思路：

使用stack来保存未匹配的“括号”的下标，然后求下标之间的最大差值。

c++ code:

class Solution { public: int longestValidParentheses(string s) { int n = s.length(); stack<int> st; for (int i = 0; i < n; i++) { if (s[i] == '(') st.push(i); else { if (!st.empty()) { if (s[st.top()] == '(') st.pop(); else st.push(i); } else st.push(i); } } int a = n, b = 0; int ans = 0; while(!st.empty()) { b = st.top(); st.pop(); ans = max(ans, a-b⑴); a = b; } ans = max(ans, a); return ans; } };

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 第三章网络体系结构

下一篇 一个操作系统的实现(6)-初识分页机制

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点