LeetCode 32. Longest Valid Parentheses题解（暴力）

我就是我 2024-04-17 22:55 7阅读 0赞

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

看到题目也就是找出左右括号能够完美闭合的最长子串，那么首先先不想别的，思考满足条件的子串，应该是左括号的数目等于右括号的数目，那么用一个标记记录左括号数，有左括号加一，右括号减一，然后我们开始一一遍历每种 i - j 的区间里的 i 开头的最长符合串，不需要考虑说 i - j 区间里还可能有子串，因为，i 遍历到后面那些子串也会被涵盖到。

代码如下：

class Solution {
    public:
        int longestValidParentheses(string s) {
            //满足左括号栈为0，则添加个数入子串
            //i表示起始坐标，j表示结束坐标
            //(leftParenthesis == 0)就代表满足条件，因为左括号和右括号数目一致
            int len = s.length();
            string left = "(";
            string right = ")";
            int maxNum = 0;
            for(int i = 0; i < len; i++){
                //左括号栈
                int leftParenthesis = 0;
                
                for(int j = i; j < len; j++){
                    if(s[j] == left[0]) leftParenthesis += 1;
                    else if(s[j] == right[0]) leftParenthesis -= 1;
                    //如果小于0说明中断了，break掉
                    if(leftParenthesis < 0) break;
                    //满足条件，判断最大
                    if(leftParenthesis == 0){
                        int tmp = j - i + 1;
                        if (tmp > maxNum) maxNum = tmp;
                    }
                    
                }
            }
            return maxNum;
        }
    };

![20190902161543415.png][]

当然暴力的解法，就是跑的很慢，空间消耗多。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/3db362f6135e4fda8b5401f23898c6ca.png
[20190902161543415.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/061aad634d4c45ea9a6d17f1ed7e1cd9.png