题目链接：. - 力扣（LeetCode）
这道题，我看了一种解法，觉得很好，来分享一下
这道题主要是 思考 当前 ) 与之匹配 ( 在哪里 ，记录下来，最后比较最大值
例子：
第一个右括号，由于没有与之匹配的左括号，所以不记录，但要更改起始位置
第一个左括号入栈，记录下标
第二个右括号有与之匹配的左括号，max = 2
第二个左括号入栈
第三个右括号，最长与之匹配的左括号是第一个左括号 max = 当前位置 - 起始位置 + 1
第四个右括号，没有与之匹配的左括号
难点在于：起始位置怎么变：当右括号进入，并且栈里没有左括号时，起始位置发生改变
例子：( ( ) ( )
主要是最后一个右括号与之匹配的左括号为第二个左括号
但是第二个左括号会被踢出去
所以找第一个左括号
由此代码写出：
typedef struct Stack
{
int* arr;
int size;
int top;
}ST;
void StackInit( ST* obj )
{
obj->arr = (int*)malloc(sizeof(int)*30005);
obj->size = 0;
obj->top = -1;
}
void StackPush( ST* obj , int pi )
{
obj->arr[++obj->top] = pi;
obj->size++;
}
void StackPop( ST* obj )
{
obj->size--;
obj->top--;
}
int StackTop( ST* obj )
{
return obj->arr[obj->top];
}
bool StackIsEmpty( ST* obj )
{
return obj->size==0;
}
int longestValidParentheses(char* s) {
ST obj;
StackInit( &obj);
int i = 0;
int max = 0;
int start = 0;
for( i = 0 ; s[i] != '\0' ; i++)
{
if( s[i] == '(' )
{
StackPush( &obj,i);
}
else
{
if( StackIsEmpty(&obj) )
start = i + 1;
else
{
StackPop(&obj);
if( StackIsEmpty(&obj) )
{
max = fmax ( max , i - start + 1 );
}
else
{
max = fmax( max , i - StackTop(&obj) );
//这里要解释一下，为什么会写StackTop , 首先要明确删除的元素与取得元素是相邻的关系
//如果是这个关系 )() 并且左括号栈不为空 那么这两个必然会匹配或者start移动（就要为空）
// 第一种情况 ())() 此时为空，并且start移动
// 第二种情况 ()() 此时左括号栈为空
// 这两种情况均已已知条件不符
}
}
}
}
return max;
}
