Longest Valid Parentheses

题目

Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

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

Example 2:

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

解题报告

理解题意

• 给定字符串，只包含：( , )
• 要求找出最长的合法的括号对长度

理解例子

• (() = 2
• 第一个 ( 不能与后面的组成合法括号对，所以最长为 2
• )()()) = 4
• 因为只有中间的两对为合法括号对，因此为 4

思路

• 括号配对一般都用栈 : stack
• 既然是计数，就得知道从哪个地方开始，匹配的括号肯定是以 ( 作为初始值，但要求最长就肯定得知道什么时候连续匹配被截断
• 如果有匹配的 () 那么就会以(为计数的起点计数。
• 如果没有匹配的 () 像 ) 计数就得从头开始
• 需要保存到目前为止的最大值

代码

栈

class Solution {
    int longestValidParentheses(string& s) {
        stack<int> stk_;
        int ans = 0, start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i]=='('){
                stk_.push(i);
            } else {
                if (stk_.empty()) {
                    start = i + 1;
                }
                int curLen = stk_.empy() ? i - start + 1 : i - stk.top();
                ans = max(ans, curLen);
            }
        }
    }
};

时间复杂度

遍历次数：O(n)，因此是线性时间，每个元素只遍历一次

空间复杂度

O(n) 表示栈的大小