32. 最长有效括号

题意：

解题思路：

思路：
1、若当前元素是'('，则入栈
2、若是')'时，说明前面一个括号有可能是'('
2.1、若栈顶元素能和')'匹配，直接将栈顶元素pop出，则当前元素i与pop元素后的栈顶元素之间的长度是以i结尾的最长有效括号的长度
2.2、若栈顶元素不能和')'匹配，则直接加入到栈中

PHP代码实现：

class Solution {
    function longestValidParentheses($s) {
        $max = 0;
        $dp = array_fill(0, strlen($s), 0);
        for ($i = 1; $i < strlen($s); $i++) {
            if ($s[$i] == ')') {
                //右括号前边是左括号
                if ($s[$i - 1] == '(') {
                    $dp[$i] = ($i >= 2 ? $dp[$i - 2] : 0) + 2;
                    ///右括号前边是右括号，并且除去前边的合法序列的前边是左括号
                } else if ($i - $dp[$i - 1] > 0 && $s[$i - $dp[$i - 1] - 1] == '(') {
                    $dp[$i] = $dp[$i - 1] + (($i - $dp[$i - 1]) >= 2 ? $dp[$i - $dp[$i - 1] - 2] : 0) + 2;
                }
                $max = max($max, $dp[$i]);
            }
        }
        return $max;
    }
    //输入: ")()())"
    /*) start = 0;
    ( start = 1; stack->top = 1;
    ) max = 2;
    ( stack = 3;
    ) max = 4*/
    function longestValidParentheses1($s) {
        $res = 0;
        $start = 0;
        $stack = new SplStack();
        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i] == '(') {
                $stack->push($i);
            } else {
                if ($stack->isEmpty()) {
                    $start = $i + 1;
                } else {
                    $stack->pop();
                    $res = $stack->isEmpty() ? max($res, $i-$start+1):max($res, $i-$stack->top());
                }
            }
        }
        return $res;
    }
}

GO代码实现：

func longestValidParentheses(s string) int {
    stack := []int{}
    stack = append(stack, -1)
    max := 0
    for i, c := range s {
        if c == '(' {
            stack = append(stack, i)
        } else {
            stack = stack[:len(stack)-1] // 弹出栈顶元素
            if len(stack) == 0 { 
                stack = append(stack, i)
            }
            // 当前元素的索引与栈顶元素作差，获取最近的括号匹配数
            max = Max(max, i - stack[len(stack)-1]) 
        }
    }
    return max
}
func Max(a, b int) int {
    if a > b {
        return a
    }
    return b
}