【栈】LeetCode-32. 最长有效括号

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)