【力扣刷题】32. 最长有效括号

灰太狼 2023-09-28 13:06 5阅读 0赞

**目录**

题目：

方法一：

解题思路：

代码：

方法二：

解题思路：

代码：

### 题目： ###

给你一个只包含 `'('` 和 `')'` 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

![b9b431f44b654204b9cd7586b657cc6d.png][]

### 方法一： ###

#### 解题思路： ####

利用栈，学过利用栈来判断一个只包含'('和')'的字符串是否是括号匹配的，那个题目解题就是，遍历整个字符串，是左括号就入栈，是右括号则①判断栈是否有左括号且弹出一个左括号，②如果栈为空则为false，如果所有字符都遍历完了，栈中还有元素则为false，否则为true。

利用这个思路，增加一个标记数组arr，初始化所有元素为1，栈中存的是数组下标（字符索引）。遍历整个字符串，如果是左括号则把索引下标（i）加入栈，如果是右括号则判断栈中元素是否为空且不为空则弹出，并把标记数组对应的元素arr\[stack.pop()\]以及当前下标对应的标记数组元素arr\[i\]置为0。

最后判断标记数组arr的最长连续0就可以了。

#### 代码： ####

class Solution {
        public int longestValidParentheses(String s) {
            //要找最长的有效括号
            //栈
            //利用栈来标记左右括号是否有效，栈的内容存下标i
            Stack<Integer> stack = new Stack<>();
            int[] valid = new int[s.length()];
            for(int i = 0; i < s.length(); i++){
                valid[i] = 1;
            }
            for(int i = 0; i < s.length();i++){
                if(s.charAt(i) == '(') stack.push(i);
                else{
                    if(!stack.empty()){
                        valid[i] = 0;
                        valid[stack.pop()] = 0;
                    }
                }
            }
            int res = 0,count = 0;
            for(int i = 0; i < s.length();i++){
                if(valid[i] == 1) {
                    count = 0;
                }else{
                    count++;
                }
                res = Math.max(res,count);
            }
            return res;
        }
    }

### 方法二： ###

#### 解题思路： ####

动态规划，利用dp\[i\]表示**以下标i字符结尾的最长有效括号的长度**。将dp数组全部初始化为0。有效的子串一定以**')'**结尾，以**'('**结尾的子串对应的dp值必定为0。所以只需要求解以')'在dp数组中对应位置的值。所以从前往后遍历字符串，求解dp值。

①s.charAt(i)=')'且s.charAt(i-1)='('，字符串为"...()"则dp\[i\] = dp\[i-2\]+2。

②如果s.charAt(i) = ')'且s.charAt(i-1) = ')'，比如字符串"...))"->"**()**((**))**"，

如果**s.charAt(i - dp\[i - 1\] - 1)='('**，那么有效括号长度新增长度2，i位置对最长有效括号长度为 i-1位置的最长括号长度加上当前位置新增的2，不过得**注意**，i − dp\[i − 1\] − 1 和 i 组成了有效括号对，这将是一段**独立的有效括号序列**，如果之前的子序列是形如 (...)(...) 这种序列，那么当前位置的最长有效括号长度还需要加上这一段。例如：**()****(())，**左边红色的和右边绿色的为两个独立的有效括号序列。所以状态转移方程为：dp\[i\] = dp\[i - 1\] + 2 + dp\[i - dp\[i - 1\] -2 \]。

图示：

![f584ad65a52d47b99c82a0d3cfa6b057.png][]

还要注意边界值，因为要用到 dp\[ i - 2 \]，还有dp\[ i - dp\[ i - 1 \] - 2 \]，要判断。

#### 代码： ####

class Solution {
        public int longestValidParentheses(String s) {
            //动态规划
            //dp[i]表示以下标i字符结尾的最长有效括号的长度
            int res = 0;
            int[] dp = new int[s.length()];
            for(int i = 1;i < s.length();i++){
                if(s.charAt(i) == ')'){
                    if(s.charAt(i-1) == '('){
                        if(i >= 2) dp[i] = dp[i - 2] + 2;
                        else dp[i] = 2;
                    }else if(i - dp[i - 1] > 0  && s.charAt(i - dp[i - 1] - 1) == '('){
                        if(i - dp[i - 1] >= 2) dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                        else dp[i] = dp[i - 1] + 2;
                    }
                }
                res = Math.max(res,dp[i]);
            }
            return res;
        }
    }

方法二看了看解析，不太会写动态规划，下次找个机会专门练一练动态规划的题目。

[b9b431f44b654204b9cd7586b657cc6d.png]: https://img-blog.csdnimg.cn/b9b431f44b654204b9cd7586b657cc6d.png
[f584ad65a52d47b99c82a0d3cfa6b057.png]: https://img-blog.csdnimg.cn/f584ad65a52d47b99c82a0d3cfa6b057.png