栈-leetcode32：Longest Valid Parentheses

一、问题描述
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example1：
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example2：
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

二、解决思路
思路一：直接用暴力法，双重循环求出字符串每一个子字符串是否是有效字符串，判断有效字符串可以使用栈来操作，最后统计最长有效子字符串，O(n^2)
思路二：思路一的时间复杂度很高，时间消耗在切分字符串上，为了降低时间复杂度，可以用空间换取时间，定义一个数组，用于存储字符串中每个字符是否是有效字符（可以匹配）
思路三：思路二中使用了额外的数组，降低思路二中的空间消耗，可以发现最长有效子字符串计算是通过当前索引位置与前面未匹配到的字符索引位置之差，因此，第一位可以使用哨兵思想，往栈中添加-1
思路四：思路二三使用栈来解决问题，为了进一步减少空间消耗，可以通过变量来替换栈，可以发现有效字符串无非就两种形式
1）()()....
2）(((....)))
通过两个left和right指针从字符串左边遍历，若字符为 '('，left++，否则right++，如果left等于right进行比较取最大值，如果right >= left，left和right重置0
同理，从字符串右侧遍历，如果left >= right，重置
为什么会需要左右两次遍历？其实这个很好理解，比如 ((()，对于从左遍历是得不到正确结果的
思路五：参考solution的动态规划思想，定义一个新数组arr，用于存储包含当前字符的子字符串的有效字符长度，当前索引 i 字符为 ')'时，会两种情况
1）前一字符为 '('，其有效长度arr[i] = arr[i - 2] + 2，前提是 i - 2 > 0
2）前一字符为 ')'，需要退到 i - arr[i - 1] - 1索引字符判断，若为 '('，其有效长度arr[i] = arr[i - 1] + arr[i - arr[i - 1] - 2] + 2，同样前提i - arr[i - 1] - 2 > 0

三、算法实现
思路二

public int longestValidParentheses(String s) {
        if(s.length() == 0 || s.length() == 1) return 0;
        Stack<Integer> stack = new Stack<>();
        int[] arr = new int[s.length()];
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0, lens = s.length(); i < lens; i++){
            char c = s.charAt(i);
            if(c == '('){
                stack.push(i);
            } else {
                if(stack.isEmpty()){
                    stack.push(i);
                } else {
                    char tp = s.charAt(stack.peek());
                    if(c == ')' && tp == '('){
                        arr[i] = 1;
                        arr[stack.pop()] = 1;
                    } else {
                        stack.push(i);
                    }
                }
            }
        }
//        for(int i = 0, lens = s.length(); i < lens; i++){
//            System.out.print(arr[i] + "\t");
//        }
//        System.out.println();
        for(int i = 0, lens = s.length(); i < lens; i++){
            if(arr[i] == 1){
                sum++;
            } else {
                max = Math.max(sum, max);
                sum = 0;
            }
        }
        // 会出现最后max遗留问题
        max = Math.max(sum, max);
        return max;
    }

思路三：

public int longestValidParentheses(String s) {
        if (s.length() == 0 || s.length() == 1) return 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max = 0;
        for(int i = 0, lens = s.length(); i < lens; i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            } else {
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }

思路四

public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right >= left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left >= right) {
                left = right = 0;
            }
        }
        return maxlength;
    }

思路五

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