Longest Valid Parentheses

LeetCode #32

Description:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example:

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.

Idea:

遇到（入栈， 遇到），如果stack空，记录位置last。如果栈非空，则pop （，然后再计算maxlen，这时候也有两种情况1. stack空，则靠last算，如果stack非空，则靠stack top位置算。

Code:

class Solution {
public:
    int longestValidParentheses(string s) {
        int last = -1;
        int max_len = 0;
        stack<int> stack_s;
        for(int i=0; i<s.size(); ++i){
            if(s[i]=='('){
                stack_s.push(i);
            }
            else{
                if(stack_s.empty()){
                    last=i;
                }
                else{
                    stack_s.pop();
                    if(stack_s.empty()){
                        max_len=max(max_len, i-last);
                    }
                    else{
                        max_len=max(max_len, i-stack_s.top());
                    }
                }
            }
        }
        return max_len;
    }
};