题解 | #最长的括号子串# [P0-T1]

栈上存目前未能pair的括号的下标

每遍历一个字符(下标i)，check是否能和栈顶下标对应的字符pair，能pair就pop栈顶。
pop完后i与栈顶的差就是截止到i的valid子串长度。
  i.e. 此时栈顶下表对应再往前一个未能pair的字符
  
举例
0 1 2 3 4 5 6 7
( ( ) ( ( ) ( ) 

i         stack      len
0         0          0
1         0 1        0
2         0          2-0 = 2
3         0 3        0
4         0 3 4      0
5         0 3        5-3 = 2
6         0 3 6      0
7         0 3        7-3 = 4

import java.util.*;

public class Solution {
  public int longestValidParentheses (String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      
      if (c == ')' && 
          !stack.isEmpty() &&
          s.charAt(stack.peek()) == '(') {
        stack.pop();  // close 1 pair
        // need to check empty again after pop
        int curLen = i - (stack.isEmpty() ? -1 : stack.peek());
        maxLen = Math.max(maxLen, curLen);
        continue;
      } 
      
      // for all other cases, (i.e. can't form a pair), push idx
      stack.push(i);
    }
    
    return maxLen;
  }
}