【栈】LeetCode-10. 正则表达式匹配

32. 最长有效括号。

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

算法分析

解题思路
栈

• 用栈维护当前待匹配的左括号的位置。同时用 start 记录一个新的可能合法的子串的起始位置。初始设为 0。
• 遇到左括号，当前位置进栈。
• 遇到右括号，如果当前栈不空，则当前栈顶出栈。出栈后，如果栈为空，则更新答案 i - start + 1；否则更新答案 i - st.peek()。
• 遇到右括号且当前栈为空，则当前的 start 开始的子串不再可能为合法子串了，下一个合法子串的起始位置是 i + 1，更新 start = i + 1。

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stk = new Stack<>();
        int ans = 0;
        for (int i = 0, start = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stk.push(i);
            } else {
                if (!stk.isEmpty()) {
                    stk.pop();
                    if (!stk.isEmpty()) {
                        ans = Math.max(ans, i - stk.peek());
                    } else {
                        ans = Math.max(ans, i - start + 1);
                    }
                } else {
                    start = i + 1;
                }
            }
        }
        return ans;
    }
}

复杂性分析

时间复杂度：O(n)
空间复杂度：O(n)