LeetCode刷题系列 -- 32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：

输入：s = ""
输出：0
 

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-valid-parentheses
 

思路：

定义单调栈 stack , 栈中用于存放元素的 index，stack 压入元素 -1 。
1. 遍历字符串，
   1.1 当遇到左括号 '(' 时, 将当前字符的位置 i 压入stack
   1.2 当遇到右括号 ')' 时，将 stack 的栈顶元素弹出。
      1.2.1 若是栈 stack 不为空，则 计算当前 有效括号子串的长度，并更新最长长度
      1.2.2 若是栈 stack 为空（此时说明需要重新压入新的标志位，计算新的有效括号），则 将当前元素的位置直接压入 stack，栈为空时 放入右括号参照物 表示从这个下标开始 需要重新计算长度

java：

class Solution {
    public int longestValidParentheses(String s) {
  Stack<Integer> stack = new Stack<>();
        // 初始参照物为 -1 ，位置 i - 初始参照物后，为其有效括号的长度
        stack.push(-1);
 
        int maxLen = 0;
        for(int i=0;i<s.length();i++) {
            if(s.charAt(i)== '(') {
                stack.push(i);
            } else {
                stack.pop();
                if(stack.empty()) {
                    // 此时需要重新压入新的标志位，计算新的有效括号
                    stack.push(i);
                } else {
                    maxLen = Math.max(maxLen,i-stack.peek()); //栈为空时 放入右括号参照物 表示从这个下标开始 需要重新计算长度
                }
            }
        }
 
        return maxLen;
    }
}