32.md

:pencil2:基础刷题之(32. Longest Valid Parentheses)

2020-02-17 吴亲库里 库里的深夜食堂

:pencil2:题目描述

**给定一个只有 '(' 和 ')' 的字符串，让我们找出最长的有效括号，题目给了两个实例。 **

:pencil2:题目实例

​

---

:pencil2:题目分析

涉及到这些括号匹配都可以使用到栈。核心就是对于 '(' 符号，将此时遍历的下标直接入栈，对于 ')',我们弹出栈顶元素，并将当前遍历的下标和栈顶元素下标求差，得出当前位置最长有效括号数。在开头位置直接先入栈一个 -1，可以自己动手试试为什么。

---

:pencil2:最终实现代码

    /**
        * @param String $s
        * @return Integer
        */
       function longestValidParentheses($s) {
           $stack=[];
           $max=0;
           array_unshift($stack,-1);
           for($i=0;$i<strlen($s);$i++){
               if($s[$i]=='('){
                   array_unshift($stack,$i);
               }else{
                   array_shift($stack);
                   if(empty($stack)){
                       array_unshift($stack,$i);
                   }else{
                       $max=max($max,$i-$stack[0]);
                   }
               }
           }
           return $max;
       }

---

联系

​