刷题主页
给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。 示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”
由题意可知该题属于括号匹配类的问题，这时就该想到使用栈解决。具体做法为：遍历字符串，遇见’(‘时便入栈，当遇到’)‘时并且位于栈顶坐标处的是’('时就将其出栈，这就会形成一个匹配括号，同时计算此时匹配括号长度即可。在代码实现中一个技巧是使用哨兵结点，即先让-1入栈，这样就可保证栈不为空，减少了许多不必要的麻烦。
class Solution { public: int longestValidParentheses(string s) { int res=0; stack<int>st; st.push(-1); for(int i=0;i<s.size();++i){ if(s[i]=='('){ st.push(i); } else{ if(st.top()!=-1 && s[st.top()]=='('){ st.pop(); res=max(res,i-st.top()); } else{ st.push(i); } } } return res; } };