[LeetCode]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 class Solution {
 2 public:
 3     int longestValidParentheses(string s) {
 4         vector<int> cache;
 5         int last = -1; //最后一个'）'
 6         int max_len = 0;
 7         for (int i = 0; i < s.size(); ++i) {
 8             if (s[i] == ')') {
 9                 if (cache.empty()) {
10                     last = i;
11                 } else {
12                     cache.pop_back();
13                     if (cache.empty()) {
14                         max_len = max(max_len, i - last);
15                     } else {
16                         max_len = max(max_len, i - cache.back());
17                     }
18                 }
19             } else {
20                 cache.push_back(i);
21             }
22         }
23         return max_len;
24     }
25 };