LeeCode 32 栈暴力

题意

传送门 LeeCode 32. 最长有效括号

题解

栈

考虑匹配的括号全部弹栈时，需要维护最长有效长度，栈底维护最近一个未被匹配的右括号的下标。若当前字符为左括号，需要等待右括号匹配，直接压栈；若为右括号，若无左括号匹配，则将其更新为新的栈底，反之匹配，跟新答案。

class Solution { public: int longestValidParentheses(string s) { int n = s.length(), res = 0; stack<int> sk; sk.push(-1); for (int i = 0; i < n; i++) { if (s[i] == ')') { sk.pop(); if (!sk.empty()) { res = max(res, i - sk.top()); } else { sk.push(i); } } else { sk.push(i); } } return res; } };

暴力

从左向右扫描，对于多余的左括号，等待匹配即可；对于多余的右括号，必然没有可匹配的左括号，则最长有效长度起点需要更新；若左括号数与右括号数相等，即相互匹配，则更新答案。

但上述方法不能处理多余左括号的情况，那么从右向左扫描，转化为对偶的问题即可。

class Solution { public: int longestValidParentheses(string s) { int n = s.length(), res = 0, l = 0, r = 0; for (int i = 0; i < n; i++) { if (s[i] == ')') { ++r; if (r > l) r = l = 0; } else ++l; if (r == l) res = max(res, r + l); } l = r = 0; for (int i = n - 1; i >= 0; i--) { if (s[i] == '(') { ++l; if (l > r) r = l = 0; } else ++r; if (r == l) res = max(res, r + l); } return res; } };