记录个人理解

题目描述

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

思路

维护一个栈，左括号位置入栈，右括号判断，一旦匹配则更新res变量，并保存当前匹配后正确括号结果。

栈中用正数表示左括号位置，负数表示已匹配连续子括号串长度。

flowchart 1[输入字符串]-->FOR[从头循环判定每个字符]-->2[是左括号?]-->|yes|当前位置入栈-->FOR 4[pop栈顶计算匹配成功长度] 2-->|no|3["栈顶是否是匹配成功括号长度？"]-->|yes|pop-->4 7[更新res]-->FOR 3-->|no|4-->5[栈顶是成功匹配长度]-->|yes|6[合并]-->7 5-->|no|长度推入栈-->7

实现-C++

 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


class Solution {
public:
    int longestValidParentheses(string s) {
        int stack[30000] = {0};
        int pos = 0;
        int  right = 0;
        int res = 0;
        while (right < s.size()) {
            if (s[right] == '(') {
                stack[pos++] = right;
            }
            else if(pos>0){
                if (pos > 1&&stack[pos-1]<0) {
                    pos--;
                }
                if (stack[pos - 1] >= 0) {
                    int tempres = right-stack[pos-1]+1;
                    int temppos = pos - 2;
                    if (temppos >= 0 && stack[temppos] < 0) {
                        tempres -= stack[temppos];
                        pos--;
                        stack[temppos] = -tempres;
                    }
                    else {
                        stack[pos - 1] = -tempres;
                    }
                    if (tempres > res)res = tempres;
                }
                else {
                    pos = 0;
                }
            }
            right++;
        }
        return res;
    }
};