[刷题防痴呆] 0032 - 最长有效括号 (Longest V

题目地址

https://leetcode.com/problems/longest-valid-parentheses/description/

题目描述

32. Longest Valid Parentheses


Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

思路

• 遍历字符串中的所有字符.
• 先push进-1作为起始.
• 若当前字符s[index]为'(', 当前index入栈.
• 若当前字符为')', 出栈. 若出栈后栈为空, 当前index入栈. 若出栈后栈不为空, 则更新max为Math.max(maxans, i - stack.peek()).

关键点

• push进-1作为起始, edge case. 作为最初的边界.

代码

• 语言支持：Java

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int max = 0;
        char[] sc = s.toCharArray();
        for (int i = 0; i < sc.length; i++) {
            if (sc[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }

        return max;
    }
}