### LeetCode 32：Longest Valid Parentheses

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

Example 1:

```Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is `"()"````

Example 2:

`Input: "`)()())`" Output: 4 Explanation: The longest valid parentheses substring is `"()()"``

（1）假如此时stack里为空，也就是没有(来和新来的)匹配，那么新来的)没啥用，也不会构成满足要求的子串，但是要记录下一个有效位置的起点，从下一位开始：lastValidIndex = i + 1

（2）假如此时stack里非空，这里又有两种情况：

A：stack里不止一个(，那么每次来一个)，就将栈顶的index出栈，直到新来的)全部匹配完，上图例子就是这种情况，用xmind记录一下逻辑

B：stack里就只剩一个(，那么新来一个)，将栈顶的index出栈，这样(被匹配光了，那么这一轮就结束了，maxLength = i – lastValidIndex + 1，比如()，lastValidInde = 0，i = 1，maxLength=2

`package com.lihuia.leetcode;import java.util.Stack;/** * Copyright (C), lihuia.com * FileName: Solution * Author:   lihui * Date:     2018/12/15 */public class Solution {    public int longestValidParentheses(String s) {        Stack<Integer> stack = new Stack<>();        int lastValidIndex = 0;        int maxLength = 0;                for (int i = 0; i < s.length(); i++) {            if (s.charAt(i) == '(') {                stack.push(i);            } else {                if (stack.empty()) {                    lastValidIndex = i + 1;                } else {                    stack.pop();                    if (! stack.empty()) {                        maxLength = i - stack.peek() > maxLength ? i - stack.peek() : maxLength;                    } else {                        maxLength = i - lastValidIndex + 1 > maxLength ? i - lastValidIndex + 1 : maxLength;                    }                }            }        }        return maxLength;    }}`