[C++知识库]【Leetcode】32. 最长有效括号

一. 题目信息

1. 描述

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
题目链接：https://leetcode-cn.com/problems/longest-valid-parentheses/

2. 示例

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

二. 解法

1. 栈

算法思路：将坐标压入栈中

①. 复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

②. c++解法

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> pos;
        pos.push(-1);
        int maxnum = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                pos.push(i);
            } else {
                pos.pop();
                if (pos.empty()) {
                    pos.push(i);
                } else {
                    maxnum = max(maxnum, i - pos.top());
                }
            }
        }
        return maxnum;
    }
};