By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、最长有效括号

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

示例 1:

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

示例 2:

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

1.1、解题思路

有效括号一次放在栈中，然后从中取出来。再栈的底部保留一个 ) 或者 -1,用来截取有效括号的长度

1584338157177

1584338205754

1584338233404

1584338259442

1584338280105

1584338343182

1584338350553

1584338359322

1584338370015

1584338379721

1584338386345

1.2、算法

    public int longestValidParentheses(String s) {
        int max = 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 {
                //正常情况下，出栈的是( ，但是这个时候栈里面是 -1 或者是 ) 那么取出来栈就变成空了，所以如果是空的情况，还会把它放进去
                stack.pop();
                if (stack.empty()) {
                    //不能让栈变成空，因为有值的情况才能进行截取
                    stack.push(i);
                } else {
                    //截取长度
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }

1.3、测试

  @Test
    public void test() {
        System.out.println(longestValidParentheses("()"));
    }

1

ContactAuthor