content: package question0032_longest_valid_parentheses;
  
  import java.util.Stack;
  
  /**
   * https://leetcode-cn.com/problems/longest-valid-parentheses/
   *
   * 栈的应用。
   *
   * 时间复杂度和空间复杂度均是O(n)，其中n为字符串s的长度。
   *
   * 执行用时：8ms，击败49.85%。消耗内存：37.7MB，击败81.56%。
   */
  public class Solution1 {
      public int longestValidParentheses(String s) {
          int result = 0, begin = 0;
          Stack<Integer> stack = new Stack<>();
          for (int i = 0; i < s.length(); i++) {
              if (s.charAt(i) == '(') {
                  stack.push(i);
              } else {
                  if (stack.isEmpty()) {
                      begin = i + 1;
                  } else {
                      stack.pop();
                      if (stack.isEmpty()) {
                          result = Math.max(result, i - begin + 1);
                      } else {
                          result = Math.max(result, i - stack.peek());
                      }
                  }
              }
          }
          return result;
      }
  }