LeetCode -- 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.
思路:
1.遍历s[i] ,i∈[0,n)并使用stack存当前索引i
2.如果s[i] 为 ')' 且stack不为空 且s[stack.Peek()] 为'('
:stack弹出
如果stack为空 , max = i + 1
否则,max = Max(max,i-stack.Peek())
否则(即s[i]为'('),直接将s[i]入栈
实现代码:
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.
思路:
1.遍历s[i] ,i∈[0,n)并使用stack存当前索引i
2.如果s[i] 为 ')' 且stack不为空 且s[stack.Peek()] 为'('
:stack弹出
如果stack为空 , max = i + 1
否则,max = Max(max,i-stack.Peek())
否则(即s[i]为'('),直接将s[i]入栈
实现代码:
public class Solution {
public int LongestValidParentheses(string s) {
int max = 0;
var stack = new Stack<int>();
for (int i = 0; i < s.Length; i++) {
if (s[i] == ')' && stack.Count > 0 && s[stack.Peek()] == '(') {
stack.Pop();
if (stack.Count == 0){
max = i + 1;
}
else{
max = Math.Max(max, i - stack.Peek());
}
} else {
stack.Push(i);
}
}
return max;
}
}