Share my 8ms concise soln. I think the problem is really hard if not thinking it in the right way


  • 0
    class Solution {
    public:
    int longestValidParentheses(string s) {
        stack<int> pos;
        int res=0;
        int size=s.length();
        int start=-1;
        for(int i=0; i<size; ++i){
            if(s[i]=='('){
                pos.push(i);
            }
            else if(!pos.empty()){
                pos.pop();
                res=max(res, pos.empty()?i-start:(i-pos.top()));
            }
            else{
                start=i;
            }
        }
        return res;
    }};
    

    I'm surprised that if using vector instead of stack, it will be 12ms. Anyone has any idea about it?



    The idea is we need to store the position of opening parentheses, so that whenever we pop it out, we know the longest valid parentheses. But we should also pay attention to one special case, if there is closing parentheses firstly, we know we should count the left valid parentheses from there instead of from the beginning.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.