32. Longest Valid Parentheses

Question

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

Solution

如果有右括号先出现于左括号，则其永远无法配对。
而如果是左括号先出现，则其有可能可以和之后的右括号进行配对。

因此我们可以将左括号的位置入栈，等待配对。
并记录上一个不能配对的右括号的位置。以此来确定当前位置的有效括号长度。

首先将上一个不能组队的右括号lastRightParenthese初始化为-1。
初始化一个最大有效长度best。

然后遍历字符串：

• 当遇到左括号时：
  • 将当前下标i压入栈。（记录等待配对的左括号）
• 遇到右括号时：
  • 如果栈为空，则更新上一个不能组队的右括号的位置为当前下标i。（此时出现的右括号一定无法配对）
  • 如果栈不为空，则挤出上一个左括号的下标，与右括号配对。
    • 挤出上一个左括号后，如果栈为空。则将当前的有效括号总长度为i - lastRightParenthese。（当前的右括号和上一个不能配对的右括号的差）
    • 否则当前的有效括号总长度为i - stack.peek()。（当前的右括号和上一个不配对的左括号的差。）

Code

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new LinkedList<>();
        int best = 0;
        int lastRightParenthese = -1;   //上一个不能配对的右括号位置，初始化为-1
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){ //如果当前位置是左括号，则将下标入栈
                stack.push(i);
            }
            else{   //如果当前位置是右括号...
                if(stack.isEmpty()){    //如果没有可以配对的左括号，则更新不能配对的右括号的位置
                    lastRightParenthese = i;
                }
                else{
                    stack.pop();    //如果有可以配对的右括号，则从栈中挤出
                    if(stack.isEmpty()){    //挤出后如果没有剩余的左括号了，则当前有效括号长度为当前位置减去上一个无法配对的右括号的位置
                        best = Math.max(best, i - lastRightParenthese);
                    }
                    else{   //如果挤出后栈内仍有剩余的左括号存在，则当前有效括号长度为当前位置减去栈顶的左括号的位置
                        best = Math.max(best, i - stack.peek());
                    }
                }
            }
        }
        return best;
    }
}