0%

[Leetcode]32. Longest Valid Parentheses(C++)

题目描述

题目链接:32. Longest Valid Parentheses

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

例子

例子 1

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

例子 2

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

解题思路

这道题可以用栈结合动态规划解决。我们维护一个栈和一个变量 start表示最近一个合法子串的起始位置:

  • 遇到 (:压入栈中
  • 遇到 ):判断当前栈是否为空:
    • 栈为空:当前下标不合法,更新 start
    • 栈不为空,表示当前右括号可以匹配,先将最近一个左括号推出,然后更新结果,通过判断栈是否为空:
      • 栈为空:我们则利用 start 来更新:maxLen = max(maxLen, i - start + 1)
      • 否则我们利用栈顶下标更新:maxLen = max(maxLen, i - index.top())

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <string>
#include <stack>

class Solution {
public:
int longestValidParentheses(std::string s) {
std::stack<int> index;
int start = 0;
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
index.push(i); // need to find a match otherwise invalid
}
else {
if (!index.empty()) {
index.pop();
maxLen = index.empty() ? std::max(maxLen, i - start + 1) : std::max(maxLen, i - index.top());
} else {
start = i + 1; // update new valid begin pos
}
}
}
return maxLen;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 32.LongestValidParentheses.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions