LeetCode -- Longest Valid Parentheses

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]入棧




實現代碼：

public class Solution {
    public int LongestValidParentheses(string s) {
        int max = 0;
        var stack = new Stack();
        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;
    }
}