LeetCode 之 Longest Valid Parentheses（栈）

爱被打了一巴掌 2022-08-02 13:56 119阅读 0赞

【问题描述】

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

For `"(()"`, the longest valid parentheses substring is `"()"`, which has length = 2.

Another example is `")()())"`, where the longest valid parentheses substring is `"()()"`, which has length = 4.

1.【基础知识】  
压栈、弹栈机制能够很好的模仿括号配对。

2.【屌丝代码】

*  完成失败！
 *  达成思想：

> 1）字符串截取，取到第一个'('为字符串首元素；
> 
> 2）字符串的元素小于等于1，合法长度判断为0；
> 
> 3）依次查找每一个正括号为首元素最长合法长度。

*  卡壳部分

> 1）未能按'('间隔，迭代实现每一个正括号为首元素的最长合法长度。

3.【AC源码】

// LeetCode, Longest Valid Parenthese
    // 使用栈，时间复杂度 O(n)，空间复杂度 O(n)
    class Solution {  
        public:  
            int longestValidParentheses(string s) {  
                int max_len = 0, last = -1; // the position of the last ')'  
                stack<int> lefts; // keep track of the positions of non-matching '('s  
                for (int i = 0; i < s.size(); ++i) { 
    				
                    if (s[i] =='(') 
    				{  
                        lefts.push(i);  
                    }   
                    else 
    				{  
                        if (lefts.empty()) 
    					{  
                            // no matching left  
                            last = i;  
                        }   
                        else 
    					{  
                            // find a matching pair  
                            lefts.pop();  
                            if (lefts.empty())
    						{  
                                max_len = max_len>=i-last?max_len:i-last;  
                            }   
                            else
    						{  
                                // lefts.top() 表示上一个未匹配的正括号
    							// i-lefts.top() 表示已匹配括号长度
    							max_len = max_len>=i-lefts.top()?max_len:i-lefts.top();  
                            }  
                        }  
                    }
                }  
            return max_len;  
        }  
    };

4.【复盘】

> 1）脑子没想好就不要动手写代码，写代码也是信马由缰毫无效率，思路不成熟的上手，在有限时间内，对任务的完成只会徒增恐惧感与无助感；
> 
> 2）对于一个没想清楚的问题，去反问一句这是不是关键问题，如果是，就把它想透再下手！
> 
> 比如本例：最相近的两个符号找到之后，它们是不是一定成对，如果成对接下去是怎么办？之前和之后的操作分别是什么？！坚决将这个问题的求解出来的态度是伟大光荣而正确的！
> 
> 因此，最先应该思考的不是问题，而是第一个元素怎么开始，进而中间的数值怎么半，边界值会让你关注细节而忽略宏观！
> 
> 3）因为笔者总有string.find()方法在脑子里面绕，这只是看起来使循环似乎变得简单，只是表面上觉得比简单的i++快。实质上这并不减少计算的时间，往往还会因为方法的调用而费时耗存！
> 
> 4）为什么这里的成员函数的字符串不是作为常量字符串的？窃以为，将字符串作为参数输入，不如将 const string 作为输入更合理！

5.【算法核心思想】

> 1）从字符串第一个元素开始，正压栈反弹栈；
> 
> 2）当次循环未压栈，且栈空，说明出现连续空栈，成对失连；
> 
> 3）当次循环未压栈，弹栈后栈空，成对暂未失连，则计算当次连续对相对上次失连元素递增数，录入；
> 
> 4）当次循环未压栈，弹栈后栈非空，成对情况未失连，则计算当次连续对相对栈顶元素递增数，录入。