leetcode热题100 P32 最长有效括号

---

时间轴

时间轴

2026-03-21

init

动态规划，栈

---

题目：

P416 分割等和子集

https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked

• 用栈模拟一遍，将所有无法匹配的括号的位置全部置1,
  • 例如:()(()的mark为[0, 0, 1, 0, 0]
  • 再例如:)()((())的mark为[1, 0, 0, 1, 0, 0, 0, 0]
• 经过这样的处理后, 此题就变成了寻找最长的连续的0的长度

#include <string>
#include <vector>
#include <stack>

using std::string;
using std::vector;
using std::stack;

class Solution {
    public:
        int longestValidParentheses(string s)
        {
                int i, j, n = s.size();
                int max_len = 0;
                stack<int> stk;
                vector<int> arr(n, 0);

                for (i = 0; i < n; i++) {
                        if (s[i] == '(') {
                                stk.push(i);
                        } else {
                                if (stk.empty())
                                        arr[i] = 1;
                                else
                                        stk.pop();
                        }
                }
                while (!stk.empty()) { //未匹配的括号
                        arr[stk.top()] = 1;
                        stk.pop();
                }
                // 找最长连续为0
                i = 0;
                while (i < n) {
                        if (arr[i] == 0) {
                                j = i;

                                while (j < n && arr[j] == 0)
                                        j++;

                                max_len = std::max(max_len, j - i);
                                i = j + 1;
                        } else {
                                i++;
                        }
                }

                return max_len;
        }
};