LeetCode 32. 最长有效括号（Longest Valid Parentheses）

题目描述

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"

输出: 2

解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"

输出: 4

解释: 最长有效括号子串为 "()()"

解题思路

设置一个栈保存字符串当前位置之前的所有'('的索引，并维护当前有效括号的前一个索引以及最长有效括号长度。每当遇到一个'('就将其索引入栈，遇到')'则分为两种情况：

• 若此时栈为空，说明此位置一定不在有效括号内，更新当前有效括号的前一个索引；
• 若栈不为空，则弹出栈顶索引，此时此位置一定在当前有效括号内。若出栈后栈变为空，则有效括号长度可从最初位置算起；若不为空，则有效括号长度需从当前栈顶索引之后算起

代码

 class Solution {

 public:

     int longestValidParentheses(string s) {

         stack<int> st;

         int maxLen = , left = -;

         for(int i = ; i < s.length(); i++){

             if(s[i] == '(') st.push(i);

             else{

                 if(st.size()){

                     st.pop();

                     if(st.empty()) maxLen = max(maxLen, i - left);

                     else maxLen = max(maxLen, i - st.top());

                 }

                 else left = i;

             }

         }

         return maxLen;

     }

 };