时间轴

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的长度
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
        }
};