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.


题意：

给定字符串（字符串只包括 '(' 和 ')' 元素）。查找最长的有效字串，即 '(' 和 ')' 匹配的最长字串。


思路：
1）创建栈，碰到匹配的括号时，弹出栈顶元素；否则，。

2）创建数组，当出栈动作发生时，把到目前为止的入栈次数与出栈次数的差值存入数组中。

3）数组处理。获取最长字串。


A）字符串模式))(()))((()))对应数组为：32543B）字符串模式))()())()()()对应数组为：22333C）字符串模式))())()((()))对应数组为：23543D）字符串模式))(()))(())()对应数组为：32433由上可知：模式匹配基本就只有1，嵌套(())2，平级()()第一种方式的数组会出现递减方式，第二种方式的数组元素会出现保持不变的。一旦出现不匹配的，那么只有push动作存在，遇到pop时中间push和pop的差肯定是增涨的。可是如果中间都是匹配的，那么最终push和pop的差不会涨。获取最长字串的方法：获取递减序列，纪录递减序列长度，并纪录递减序列开始的首元素和尾元素。从纪录的首元素开始往前查找，直到遇到的元素小于纪录的尾元素，记前驱长度。递减序列长度＋前驱长度＝字串长度。



structstack{charword;structstack*next;};structstack*push(structstack*head,charword){structstack*node=(structstack*)malloc(sizeof(structstack));if(!node){printf("createnodeerror\n");returnhead;}node->word=word;if(!head){node->next=NULL;head=node;}else{node->next=head;}returnnode;}structstack*pop(structstack*head){if(!head){returnhead;}structstack*del=head;head=head->next;free(del);returnhead;}chartop(structstack*head){if(!head){return0;}returnhead->word;}voidstackFree(structstack*head){if(!head){return;}structstack*del=NULL;while(head){del=head;head=head->next;free(del);}}intlongestValidParentheses(char*s){if(!s){return0;}intsize=strlen(s)/2+1;intsub[size];intindex=0;structstack*head=NULL;intpushNum=0;intpopNum=0;intflag=0;for(;*s;s++){if(*s=='('){head=push(head,*s);pushNum+=1;flag=0;}elseif(*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){returnindex*2;}intlength=0;intmaxLen=0;intcnt=0;intmin=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;}}returnmaxLen*2;}

注意栈内存的释放