美文网首页
[刷题防痴呆] 0032 - 最长有效括号 (Longest V

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

作者: 西出玉门东望长安 | 来源:发表于2022-03-12 00:16 被阅读0次

题目地址

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;
    }
}

相关文章

网友评论

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

      本文链接:https://www.haomeiwen.com/subject/etzqdrtx.html