LeetCode 32 Longest Valid Parentheses

思路

用stack存左括号和没匹配上的右括号的索引。
遇到左括号：直接入栈。
遇到右括号：（1）若栈为空，则直接入栈
（2）若栈不为空：看栈顶元素是否为左括号，若为左括号，则pop并且max = i-peek()；【其中若弹栈后栈空了，则i-(-1)】

复杂度

时间复杂度O(n), 空间复杂度O(n)

代码

class Solution {
    public int longestValidParentheses(String s) {
    if(s == null || s.length() == 0)return 0;// use a stack to track the index of all unmatched parenthesesStack<Integer> stack = new Stack<>();int max = 0;for(int i = 0; i < s.length(); i++) {
    if(s.charAt(i) == '(') {
    stack.push(i);} else {
    // s.charAt(i) == ')'if(stack.isEmpty()) {
    stack.push(i);} else {
    // not emptyif(s.charAt(stack.peek()) == '(') {
    stack.pop();int indexTop = stack.isEmpty() ? -1 : stack.peek();max = Math.max(max, i - indexTop);} else {
    stack.push(i);}}}}return max;}
}