[Leetcode][第32题][JAVA][最长有效括号][动态规划][栈][正向逆向结合]

约定不等于承诺〃 2023-02-22 13:51 5阅读 0赞

#### 【问题描述】\[困难\] ####

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
    
    示例 1:
    
    输入: "(()"
    输出: 2
    解释: 最长有效括号子串为 "()"
    示例 2:
    
    输入: ")()())"
    输出: 4
    解释: 最长有效括号子串为 "()()"

#### 【解答思路】 ####

###### 1. 动态规划 ######

动态规划流程  
第 1 步：设计状态  
dp\[i\] 表示以下标 ii 字符结尾的最长有效括号的长度  
第 2 步：状态转移方程  
“……()”：s\[i\]=‘)’ 且 s\[i−1\]=‘(’ dp\[i\]=dp\[i−2\]+2  
“……))”：s\[i\]=‘)’ 且 s\[i−1\]=‘)’ 且 s\[i−dp\[i−1\]−1\]=‘(’ dp\[i\]=dp\[i−1\]+dp\[i−dp\[i−1\]−2\]+2  
第 3 步：考虑初始化  
注意 边界问题 i>=0  
第 4 步：考虑输出  
maxans = Math.max(maxans, dp\[i\]);  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200704105418714.png]

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

###### 2. 栈 ######

辅助 不符合条件时要中断  
遇到“（”把当前遍历i下标入栈  
遇到“）”出栈 空时证明子串中断 非空 计算深度 i - stack.peek()  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200704110042475.png]

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

###### 3. 正向逆向结合 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][20200704110053999.png]

public class Solution { 
        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;
        }
    }

#### 【总结】 ####

###### 1.动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2.栈 计算长度的题目 可以以字符串位置下标入栈 引入辅助栈（长度开始的下标） ######

###### 3. 正向逆向结合 好方法 好思想 灵活运用 ######

转载链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200704105022733.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200704105418714.png]: https://img-blog.csdnimg.cn/20200704105418714.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200704105509554.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200704110042475.png]: https://img-blog.csdnimg.cn/20200704110042475.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020070411002530.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200704110053999.png]: https://img-blog.csdnimg.cn/20200704110053999.png