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

题目描述

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())

代码如下：

#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