给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()" struct PosStack{ int pos; struct PosStack *next; }; static struct PosStack * push_into_stack(int val,struct PosStack *head) { struct PosStack *new_stack=(struct PosStack *)malloc(sizeof(struct PosStack)); new_stack->pos=val; new_stack->next=head; head=new_stack; return head; } static int pop_from_stack(struct PosStack **head) { if(!*head)return -1; int ret=(*head)->pos; struct PosStack *tmp=*head; *head=(*head)->next; free(tmp); tmp=NULL; return ret; } static void clear_stack(struct PosStack *head) { struct PosStack * tmp=NULL; while(head) { tmp=head; head=head->next; free(tmp); tmp=NULL; } } int longestValidParentheses(char * s){ int len=strlen(s); if(len<2)return 0; bool *state=(bool *)malloc(sizeof(bool)*len); memset(state,0,sizeof(bool)*len); struct PosStack *head=NULL; for(int i=0;i<len;i++) { if(s[i]=='(') { head=push_into_stack(i,head); } else { int pos=pop_from_stack(&head); if(pos==-1) { continue; } else { state[i]=true; state[pos]=true; } } } int max_size=0; int tmp_size=0; for(int i=0;i<len;++i) { if(state[i]) { tmp_size++; } else if(tmp_size!=0) { max_size=max_size>tmp_size?max_size:tmp_size; tmp_size=0; } } max_size=max_size>tmp_size?max_size:tmp_size; free(state); clear_stack(head); return max_size; }执行用时 : 12 ms, 在Longest Valid Parentheses的C提交中击败了85.04% 的用户
内存消耗 : 9.5 MB, 在Longest Valid Parentheses的C提交中击败了5.06% 的用户
