The longest valid bracket of question 32 in C language. Implement with stack

Give you one that only contains '(' and ')' String , Find the longest effective （ The format is correct and continuous ） The length of the bracket substring .

Example 1：

Input ：s = "(()"
Output ：2
explain ： The longest valid bracket substring is "()"

Example 2：

Input ：s = ")()())"
Output ：4
explain ： The longest valid bracket substring is "()()"

Example 3：

Input ：s = ""
Output ：0

Tips ：

    0 <= s.length <= 3 * 104
    s[i] by '(' or ')'

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-valid-parentheses
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Here are two ways to implement with stack ：（ The mind is the same ）

Mode one ：

arr The record appears '(' Subscript of time ,map The record appears ')' The effective length of bracket substring
Traverse ‘s’,

    yes '(' when ,arr Save the current subscript ‘i’
    yes ')' when , Take out arr Last of '(' The corresponding subscript ‘l’, Form valid parentheses , At this time, the effective bracket length is ‘cout=i-l+1’,map[i] by count, You need to consider , If it's continuous , be map[l-1] Valuable ,l yes ‘(’ The subscript that appears ,l-1 It was the last time ‘)’ The subscript that appears , here map[i]=count+map[l-1]
    Finally back to Math.max(map[i],max)

Such as ：s=")()())"
i=2 when ,arr=[1], count = i-l+1 = 2-1+1, map={2:2}, max=2
i=4 when ,arr=[3], count = 4-3+1, map[3-1] It's worth it 2, map[4]=count+map[2]=2+2,max=4

Square twelve ：（ Force deduction official method ）

Always keep the elements at the bottom of the stack in the currently traversed elements 「 The subscript of the last closing bracket that is not matched 」, This approach mainly considers the treatment of boundary conditions , Other elements in the stack maintain the subscript of the left bracket ：

    For every one of them ‘(’ , We put its subscript on the stack
    For every one of them ‘)’ , First, we pop up the top element of the stack, indicating that it matches the current closing parenthesis ：
        If the stack is empty , Indicates that the current closing bracket is a closing bracket that has not been matched , We put its subscript on the stack to update what we mentioned earlier 「 The subscript of the last closing bracket that is not matched 」
        If the stack is not empty , The subscript of the current right bracket minus the top element of the stack is 「 The length of the longest valid parenthesis ending with the closing parenthesis 」

If you want to know more basic knowledge , You can pay attention to my other blogs related to bracket matching ：

Data structure notes for postgraduate entrance examination review （ 5、 ... and ） Stacks and queues （ On ）（ Contains stack related content ）_ Take care of two dogs and never put a bad blog -CSDN Blog

 C Language force buckle 20 Parenthesis matching of questions . Implementation with stack _ Take care of two dogs and never put a bad blog -CSDN Blog

There are various classic examples

int longestValidParentheses(char* s) {
    int maxans = 0, n = strlen(s);
    int stk[n + 1], top = -1;
    stk[++top] = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            stk[++top] = i;
        } else {
            --top;
            if (top == -1) {
                stk[++top] = i;
            } else {
                maxans = fmax(maxans, i - stk[top]);
            }
        }
    }
    return maxans;
}