LeetCode Java First 400 题解

Longest Valid Parentheses    Hard

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

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

public int longestValidParentheses(String s) {

    StackInteger stack = new StackInteger();

    int max = 0;

    int left = -1;

    for (int j = 0; j s.length(); j++) {

        if (s.charAt(j) == '(')

            stack.push(j);

        else {

            if (stack.isEmpty())

                left = j;

            else {

                stack.pop();

                if (stack.isEmpty())

                    max = Math.max(max, j - left);

                else

                    max = Math.max(max, j - stack.peek());

            }

        }

    }

    return max;

}

思路:典型压栈题目。遇左括号压栈,右括号判断是否合法,合法弹出判定最大长度,不合法则把左边界右移。特殊情况:栈不为空时也有可能取得最大长度。
最新回复(0)
/jishupr_2FnZBUAQFim5oWCAKancCkAVV9ucLiOyKZEFSM_2BAsE_3D4489404
8