[LeetCode]32. Longest Valid Parentheses

32. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

題意：

給定字符串（字符串只包括 '(' 和 ')' 元素）。查找最長(zhǎng)的有效字串，即 '(' 和 ')' 匹配的最長(zhǎng)字串。

思路：
1）創(chuàng)建棧，碰到匹配的括號(hào)時(shí)，彈出棧頂元素；否則，。

2）創(chuàng)建數(shù)組，當(dāng)出棧動(dòng)作發(fā)生時(shí)，把到目前為止的入棧次數(shù)與出棧次數(shù)的差值存入數(shù)組中。

3）數(shù)組處理。獲取最長(zhǎng)字串。

A）字符串模式
)) (()) ) ((()))  對(duì)應(yīng)數(shù)組為：3 2 5 4 3

B）字符串模式
)) ()() ) ()()()  對(duì)應(yīng)數(shù)組為：2 2 3 3 3

C）字符串模式
)) () ) ()((()))  對(duì)應(yīng)數(shù)組為：2 3 5 4 3

D）字符串模式
)) (()) ) (())()  對(duì)應(yīng)數(shù)組為：3 2 4 3 3

由上可知：
模式匹配基本就只有
1，嵌套(())
2，平級(jí)()()

第一種方式的數(shù)組會(huì)出現(xiàn)遞減方式，第二種方式的數(shù)組元素會(huì)出現(xiàn)保持不變的。

一旦出現(xiàn)不匹配的，那么只有push動(dòng)作存在，遇到pop時(shí)中間push和pop的差肯定是增漲的?？墒侨绻虚g都是匹配的，那么最終push和pop的差不會(huì)漲。

獲取最長(zhǎng)字串的方法：
獲取遞減序列，紀(jì)錄遞減序列長(zhǎng)度，并紀(jì)錄遞減序列開(kāi)始的首元素和尾元素。從紀(jì)錄的首元素開(kāi)始往前查找，直到遇到的元素小于紀(jì)錄的尾元素，記前驅(qū)長(zhǎng)度。
遞減序列長(zhǎng)度＋前驅(qū)長(zhǎng)度 ＝ 字串長(zhǎng)度。

struct stack
{
    char word;
    struct stack *next;
};

struct stack
*push(struct stack *head, char word)
{
    struct stack *node = (struct stack *)malloc(sizeof(struct stack));
    if ( !node )
    {
        printf("create node error\n");
        return head;
    }
    
    node->word = word;
    if ( !head )
    {
        node->next = NULL;
        head = node;
    }
    else
    {
        node->next = head;
    }
    
    return node;
}

struct stack
*pop(struct stack *head)
{
    if ( !head )
    {
        return head;
    }
    
    struct stack *del = head;
    head = head->next;
    free(del);
    
    return head;
}

char
top(struct stack *head)
{
    if ( !head )
    {
        return 0;
    }
    
    return head->word;
}

void
stackFree(struct stack *head)
{
    if ( !head )
    {
        return;
    }
    
    struct stack *del = NULL;
    while ( head )
    {
        del = head;
        head = head->next;
        free(del);
    }
}

int
longestValidParentheses(char* s)
{
    if ( !s )
    {
        return 0;
    }
    
    int size = strlen(s) / 2 + 1;
    int sub[size];
    int index = 0;
    struct stack *head = NULL;
    int pushNum = 0;
    int popNum  = 0;
    int flag = 0;
    for ( ; *s; s++ )
    {   
        if ( *s == '(' )
        {   
            head = push(head, *s);
            pushNum += 1;
            flag = 0;
        }   
        else if ( *s == ')' )
        {   
            if ( top(head) == '(' )
            {   
                head = pop(head);
                popNum += 1;
                flag = 1;
            }   
            else
            {
                head = push(head, *s);
                pushNum += 1;
                flag = 0;
            }
        }
        if ( flag == 1 )
        {
            sub[index] = pushNum - popNum;
            index += 1;
        }
    }
    
    stackFree(head);
    
    if ( index == 1 )
    {
        return index * 2;
    }
    
    int length  = 0;
    int maxLen  = 0;
    int cnt = 0;
    int min = 0;
    for ( cnt = 0; cnt < index - 1; cnt++ )
    {
        length = 0;
        min    = -1;
        while ( (cnt + 1 + length) < index && sub[cnt + length] >= sub[cnt + 1 + length] )
        {
            length += 1;
        }
        
        while ( (cnt - 1 - min) >= 0 && sub[cnt - 1 - min] >= sub[cnt + length] )
        {   
            min += 1;
        }
        
        cnt = cnt + length;
        length = length + 1 + min;
        if ( length > maxLen )
        {
            maxLen = length;
        }
    }
    
    return maxLen * 2;
}

注意棧內(nèi)存的釋放