[数据结构与算法]LeetCode----------最长有效括号

题目链接：

链接: 最长有效括号.

题目描述：

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

测试样例：

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

示例 3：

输入：s = "(())"
输出：4
解释：最长有效括号子串是 "(())"

参考题解：

时间复杂度：O(N) ;

@Override
class Solution {
public:
    int longestValidParentheses(string s) {
        int slen = s.size();
        int laststart = 0;	// 用来记录当前连续有效括号的起始位置
        int maxlen = 0;		// 用来记录最长有效括号长度
        stack<int>start;	// 用来存'('的位置
        for(int i = 0; i < slen; ++i)	//遍历一次字符串
        {
            if(s[i] == '(') start.push(i);	// 碰到'('就将其位置入栈
            else	// 以下为碰到')'的情况
            {
                if(!start.empty())	// 碰到')'且栈不为空
                {
                    start.pop();
                    if(!start.empty())
                    {
                    	// pop完还不为空则说明原本栈内不止一个'('
                    	// 那么maxlen只能用栈顶元素来计算
                    	// 例如：'(()'
                        maxlen = max(maxlen, i - start.top());
                    }
                    else 
                    {
                    	// pop完栈为空那么maxlen只能用laststart来计算
                    	// 例如：'()()'
                    	maxlen = max(maxlen, i - laststart + 1);
                	}
                }
                else	// 碰到')'且栈为空
                {
                	// 重新开始计数，记录一下接下来的起始位置
                	laststart = i + 1;
            	}
            }
        }
        return maxlen;
    }
};

执行结果：

解题历程：

看到 括号匹配 就想到用栈来解决。一开始没想着引入 laststart 这个参数，想着用栈顶元素就可以算出 maxlen。直到 ‘()()()’ 样例出错才想到仅靠栈顶元素是无法“回忆”到第一个左括号的位置的，因此引入一个参数来记录。
总的来说，只进行了一个循环，遍历了一次输入字符串。因此，时间复杂度为O(N)。