leetCode-32 最长有效括号-Longest-Valid-Parentheses-(DP--Stack)

以你之姓@ 2023-06-21 13:27 10阅读 0赞

# leetCode-32 最长有效括号  #

![format_png][]

--------------------

一般会用到两种解法，栈和动态规划，但是两种方法都需要考虑到外层括号包裹内层括号的情况，即外层内部包含有一个完整的有效括号。

# 1、栈 #

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;
        }

一下：

1. 创建一个栈

2. 初始化返回结果为0 （maxL=0）

3. 如果是‘（’，入栈

4. 如果是 ‘）’，分如下a、b、c 三步

a) 栈顶出栈

b)  若，栈为空，入栈 i

c)  若，栈为非空，计算最大（i-currentTop）与现有的最大值，取最大：即maxans = Math.max(maxans, i - stack.peek());

具体的演示过程如下：

![20191215103029137.gif][]

# 2、动态规划 #

![format_png 1][]

![format_png 2][]

--------------------

第一个问题就是常规的思路问题，不管是从前往后还是从后往前，都是在遇到左括号才会进行考虑，栈的思路更简洁，不满足匹配条件的下标都入栈，检测到匹配的左右括号就出栈，然后将下标差值获得，取得最大值。而动态规划则是利用一种反向累加的形式来解决问题的。

python的栈解法、动态规划解法，参看：

[https://github.com/kkman2008/LeetCode/wiki/leetCode-32-%E6%9C%80%E9%95%BF%E6%9C%89%E6%95%88%E6%8B%AC%E5%8F%B7-Longest-Valid-Parentheses-(DP--Stack)][https_github.com_kkman2008_LeetCode_wiki_leetCode-32-_E6_9C_80_E9_95_BF_E6_9C_89_E6_95_88_E6_8B_AC_E5_8F_B7-Longest-Valid-Parentheses-_DP--Stack]

更多参考leetCode：

[https://leetcode.com/articles/longest-valid-parentheses/][https_leetcode.com_articles_longest-valid-parentheses]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMzc5NDA3NC03OTBjYTJiZTE3MDdmZmZjLnBuZw?x-oss-process=image/format,png
[20191215103029137.gif]: https://img-blog.csdnimg.cn/20191215103029137.gif
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMzc5NDA3NC0yZTg0MzgwYWEwN2IwODM1LnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMzc5NDA3NC0xMTRlNmY2ZmRmNTk1NzY4LnBuZw?x-oss-process=image/format,png
[https_github.com_kkman2008_LeetCode_wiki_leetCode-32-_E6_9C_80_E9_95_BF_E6_9C_89_E6_95_88_E6_8B_AC_E5_8F_B7-Longest-Valid-Parentheses-_DP--Stack]: https://github.com/kkman2008/LeetCode/wiki/leetCode-32-%E6%9C%80%E9%95%BF%E6%9C%89%E6%95%88%E6%8B%AC%E5%8F%B7-Longest-Valid-Parentheses-%28DP--Stack%29
[https_leetcode.com_articles_longest-valid-parentheses]: https://leetcode.com/articles/longest-valid-parentheses/