32. Longest Valid Parentheses

题目描述

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-valid-parentheses

乍一看挺简单，就是简单的匹配，故产生了如下代码：

错误的尝试

#include <string.h> int longestValidParentheses(char * s){ int len = strlen(s); int max = 0; int count = 0; int i; for(i = 0; i < len; i++){ if(s[i] == ')'){ continue; if(max < count)max = count; count = 0; } else{ if(s[i+1] == ')'){ count += 2; i++; if(max < count)max = count; } else{ continue; if(max < count)max = count; count = 0; } } } return max; }

本来也没什么毛病，测试样例也通过了，欣然提交，然后蹦出来一个WA。 芜湖~"(())"被视作2对有效括号了，那就又是那个经典的栈的应用了。

栈的使用

这里注意到我们还要进行计数，故使用整数栈。

#include <stack> #include <iostream> class Solution { public: int longestValidParentheses(string s) { stack<int> sta; int ans = 0; sta.push(-1); for(int i = 0; i < s.size(); i++){ if(s[i] == '('){ sta.push(i); } else{ sta.pop(); if(sta.empty()){ sta.push(i); } else{ ans = max(ans, i - sta.top()); } } } return ans; } };