|
题目
给定字符串，仅包含左括号‘（’和右括号‘）’，它可能不是括号匹配的，设计算法，找出最长匹配的括号子串，返回该子串的长度。
如：
（（）：2
（）（）：4
（）（（））：6
（（）（））：6
分析
1、记起始匹配位置start=-1；最大匹配长度ml=0；最大匹配长度是每个右括号出栈后都需要判断是否要更新的
2、考察第i位字符c
3、如果c为左括号，直接压栈。
4、如果c为右括号，分为两种情况：
一种是现有栈为空，表示没有匹配的左括号，start=i，为下一次可能的匹配做准备
另外一种情况是栈不空，这时候有括号一定和栈顶元素是匹配的，因为右括号是不允许进栈的，这时候需要出栈匹配。出站后又分为两种：
如果栈空，i-start即为当前找到的匹配长度，检查i-start是否比ml更大，是的ml得以更新。
如果栈不空，则当前栈顶元素t是上次匹配的最后位置，检查i-t是否比ml更大，使得ml得以更新。
5、注：因为入栈的一定是左括号，显然没有必要将他们本身入栈，应该入栈的是该字符在字符串中的索引。
代码如下
int GetLongestParenthese(const char* p)
{
int size = (int)strlen(p);
std::stack<int> s;
int answer = 0;
int start = -1;
for (int i = 0; i < size; i++)
{
if (p[i] == '(')
{
s.push(i);
}
else
{
if (s.empty())
{
start = i;
}
else
{
s.pop();
if (s.empty())
{
answer = max(answer, i - start);
}
else
{
answer = max(answer, i - s.top());
}
}
}
}
return answer;
}
| 
转播
