给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。
样例
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
算法分析:
栈
- 1、若当前栈为空 或者 当前元素是
'('
,则直接加入栈中 - 2、当当前元素是
')'
时,说明有和栈顶元素匹配的可能- 1、若栈顶元素能和
')'
匹配,直接将栈顶元素pop
出,则当前元素i
与pop
元素后的栈顶元素之间的长度是以i
结尾的最长有效括号的长度 - 2、若栈顶元素不能和
')'
匹配,则直接加入到栈中
- 1、若栈顶元素能和
注意:栈保存的是坐标
Java 代码
class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stk = new Stack<Integer>();
int ans = 0;
for(int i = 0;i < s.length();i ++)
{
char t = s.charAt(i);
if(stk.isEmpty() || t == '(') stk.add(i);
else
{
if(s.charAt(stk.peek()) == '(')
{
stk.pop();
if(!stk.isEmpty()) ans = Math.max(ans,i - stk.peek());
else ans = Math.max(ans,i + 1);
}
else stk.add(i);
}
}
return ans;
}
}
赞,先push进去一个 - 1,防止栈 pop 抛出异常
谢谢hh
点赞!
谢谢hh