32. 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.

解析

• 对于括号匹配，和Valid Parentheses同样的思路，用栈维护左括号，即在读取字符串的时候，遇到左括号就入栈。遇到右括号就出栈，同时判断当前括号匹配的子串是否为最长子串。不过在判断括号匹配的子串的长度的时候，有一些值得注意的问题，其中需要借助变量l记录当前括号匹配的子串的左侧位置.
• 本题使用初始-1入栈，就省去了记录记录当前括号匹配的子串的左侧位置;（（））：3-(-1)=4; 但是栈为空的时候，需要入栈当前位置，例如 ())()()=6-2=4，在str[2]='）'入栈index

class Solution_32 {public:        // 只是入栈‘（’并不能解决问题，需要入栈‘（’的下标index    int longestValidParentheses(string s) {        if (s.size()<=1)        {            return 0;        }        stack
    
      sta;        sta.push(-1); //技巧使用了初始化，否则需要记录 需要借助变量l记录当前括号匹配的子串的左侧位置        int ret = 0;        for (int i = 0; i < s.size();i++)        {            if (s[i]=='(')            {                sta.push(i);            }            else            {                sta.pop();                if (sta.empty())                {                    sta.push(i); //入栈                }                else                {                    int cur = i - sta.top();                    ret = max(ret,cur);                }            }                    }        return ret;    }};
    

题目来源