leetcode【每日一题】32. 最长有效括号 Java

题干

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

想法

栈，栈底存尚未匹配的最后一个）的位置

遍历数组
（的话直接放入栈

）的话，栈顶出去
如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

java代码

package daily;

import java.util.Stack;

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        int maxres=0;
        Stack <Integer> stack=new Stack<>();
        //初始化
        stack.push(-1);
        for (int i=0;i<s.length();i++){
            //（直接加
            if(s.charAt(i)=='('){
                stack.push(i);
            }
            else {
                stack.pop();
                //空 没有匹配
                if(stack.isEmpty()){
                    stack.push(i);
                }
                else {
                    maxres=Math.max(maxres,i-stack.peek());
                }
            }
        }
        return maxres;
    }

    public static  void main(String[] args){
        String s=")()())";
        LongestValidParentheses longestValidParentheses=new LongestValidParentheses();

        System.out.println(longestValidParentheses.longestValidParentheses(s));
    }
}

我的leetcode代码都已经上传到我的githttps://github.com/ragezor/leetcode