Created
December 19, 2017 23:21
-
-
Save jianminchen/c688daa844c6fe3622799dc437eb430d to your computer and use it in GitHub Desktop.
Leetcode 32 - longest valid parentheses - analysis from the blog: http://blog.csdn.net/worldwindjp/article/details/39460161
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
最长合法括号数 | |
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. | |
https://oj.leetcode.com/problems/longest-valid-parentheses/ | |
分析,求出一串由:‘(’和‘)’组成的字符串中最长有效括号的长度。例如:(()(),结果是4。((()))结果是6。())()()结果是4。 | |
解题思路:最容易想到的解法就是穷举法,计算任意两点(i到j)之间有多少个合法的()串,借助动态规划可以得到结果。算法复杂度为:O(n3) | |
想要O(n)的解法需要一点技巧,栈中保存的不是‘(’而是‘(’所在的index,在此基础上也要弄清楚几种情况: | |
每次来了‘(’之后,无条件压栈。如果碰到')'的话,如果栈不为空,就消除栈内剩余的'(' | |
第一:消除掉'('之后,如果栈内还有剩余的‘(’的话,最长的合法长度就是:maxLength = Math.max(i - (int)stack.peek() , maxLength); 也就是取: | |
当前')'的index减去栈顶元素的index 和 原来max_length 两者的最大值。 | |
例如:对于这种情况:()(()(),可以正确的得出最大值为4。 | |
第二:消除掉')'之后,栈内没有剩余的‘(’了。此时需要引入一个新的变量start,用于表示合法括号字符串的起点。 | |
例如:对于这种情况:())()(),可以正确的得出最大值为4。 | |
start初始为-1,之后每次碰到‘)’且栈为空的时候更新为当前‘)’的index。也就是说无法消除的)之后的括号不可能再和前面的括号合并在一起计算最长序列, | |
所以更新start。 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment