本文主要是介绍Crack LeetCode 之 32. Longest Valid Parentheses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Leetcode link: https://leetcode.com/problems/longest-valid-parentheses/description/
本题非常适合在面试中使用，因为需要面试者综合考虑各种情况，并且题目短小可以在面试时间内完成。
本题有3个要点：
1. 这类检查括号的题目一般会用栈做数据结构。左括号入栈，右括号出栈。
2. 综合考虑各种情况。例如下面代码所示，遇到左括号的情况，遇到右括号的情况，栈是否为空的情况以及出栈操作后栈是否为空的情况。
if (is left parenthesis) {//do something
}
else {if (stack is emtpy) {//do something}else {pop_stack();if (stack is emtpy) {//do something}else {//do something}}
}
3. 本题使用当前字符的位置减去序列起始位置来计算合法序列的长度。
基本算法：
首先，我们维护一个索引start，指向合法序列的第一个字符。其次，用一个循环依次扫描每个字符，循环体里做如下判断。
1. 如果是左括号，那么就入栈。
2. 如果是右括号，那么检查栈是否为空。
2.1 如果栈是空，那么说明一个合法序列已经结束，我们要把start置为当前字符i的下一个字符。
2.2 如果栈不空，那么做出栈操作。然后再判断栈是否为空。
2.2.1 如果栈是空，那么说明当前合法序列与上一段合法序列是相连的。
2.2.2 如果栈不空，那么使用栈顶元素的位置来计算合法序列的长度i - stackCheck.top()。
本算法时间复杂度是O(n)，因为只扫描一遍；空间复杂就是栈的size，也是O(n)，因为最坏情况是都是左括号。以下为C++代码和python代码：
class Solution
{
public:int longestValidParentheses(string s){if (s.empty())return 0;int start = 0;int maxCount = 0;stack<int> stackCheck;for (int i = 0; i<s.length(); ++i) {if (s[i] == '(')stackCheck.push(i);else {if (stackCheck.empty())start = i + 1;else {stackCheck.pop();int count = stackCheck.empty() ? (i - start + 1) : (i - stackCheck.top());if (count > maxCount)maxCount = count;}}}return maxCount;}
};
class Solution:def longestValidParentheses(self, s):if s is None or len(s) == 0:return 0maxcount = 0count = 0start = 0stack = []for i, v in enumerate(s):if v == '(':stack.append(i)else:if len(stack) == 0:start = i + 1else:stack.pop()if len(stack) == 0:count = i - start + 1else:count = i - stack[-1]if count > maxcount:maxcount = countreturn maxcount
这篇关于Crack LeetCode 之 32. Longest Valid Parentheses的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
