32. Longest Valid Parentheses

题目概括:

给定一个只有括号的字符串，找到最长的有效括号。
例如: "(()" -> "()"

专题: 动态优化, 栈

• 栈的解法: 时间O(n), 空间O(n)

废话不多说，先上使用栈的解法

public int longestValidParentheses(String s) {
  int maxlen = 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 {
            maxlen = Math.max(maxlen, i - stack.peek());
                }
        }
      }
       return maxlen;
}

这个解法的思路: 维持一个栈，栈中存放字符的坐标。遇到'('就推进，反之就pop出。若pop()以后，栈空了。说明目前遇到的')'比'('多一个。此时放入当前坐标(相当于锚定的作用，所以栈在初始化后，就要放入一个-1). 若pop()以后,栈不空，则可以计算当前发现的valid string 长度。

• 动态优化的解法:时间O(n), 空间O(n)

public int longestValidParentheses(String s) {
    int maxans =0 ;  
    int dp[] = new int[s.length()];
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            if (s.charAt(i - 1) == '(') {
                dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
            }else if (i - dp[i -1] > 0 && s.charAt(i - dp[i-1] - 1) == '(') {
                dp[i] = dp[i-1] + ((i - dp[i-1]) >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2;
              }
            maxans = Math.max(maxana,  dp[i]);
          }
}
  return maxans;
}

分成两种情况:

1. s[i] = ')' and s[i-1] = '(': 形如: "...........()"
   dp[i] = dp[i-2] + 2;
2. s[i] = ')' and s[i-1] = ')' and s[i- dp[i-1] - 1] = '(' : 形如: "............))"
   dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2