[Leecode] Longest Valid Parentheses Solution

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

分析

encounter brackets matching problems generally use stack. The left parenthesis is pushed onto the stack, and the right parenthesis is popped. Then the root stack is empty to determine whether it matches. We can iterate over the string, set a variable maxs that records the maximum length in the global variable, and then update maxs every time we successfully match it. In order to be able to record the length of the string each time the match is successful, it is also necessary to maintain a variable start to record the start position of the string. When traversing a string: If the left parenthesis is encountered, it is pushed onto the stack. If the right parenthesis is encountered: There are two cases:

1, the stack is empty at this time. At this time, it means that the right parenthesis cannot match the legal string, and the processing characters can be ignored. Then the beginning of the string is the position to the right of the right parenthesis.

2, the stack is not empty at this time. Popped up. Successful match. Then record the length of the matched string. And update the maximum length. How to get the length? There are two cases:

1) The stack is empty at this time. Indicates that the starting position of the matched string is start. Let i-start+1 get the string length.

2) The stack is not empty at this time. Indicates the position of the left parenthesis that matches up to the top of the stack. When the stack is pushed, the subscript of the character is pushed onto the stack, so i-top() is the length of the legal string at the moment.

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