自己解法
看到这题的第一想法就是他喵的括号又见括号，之前括号有效性的精髓就是左括号个数要大于右括号个数，所以第一想法是，遇到左括号加1，遇到右括号，左括号减一，认为有效，但这样没有考虑连续的问题，右边括号多于左边的时候进行了清空重算，但左括号多的时候怎么处理没想清楚，看了下官方题解，下面上官方题解的思路。
刚才的思路是只计算了左右括号的个数，就不想用栈了，虽然栈很多时候都是解括号题的利器哈哈，现在用栈来解，栈里保存的是当前没有变成有效括号的下标位置。遇到左括号直接下标入栈，遇到右括号时，弹出一个元素，如果此时栈不为空，就说明前一个弹出的是左括号，计算两个下标之间的距离，算出字符串长度。栈为空的情况下，就把自己压入栈中，当作最近一个无效括号的位置。
class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<Integer>();
// 堆栈存放的可以理解为最近一个无效的括号下标
stack.push(-1);
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
maxLen = Math.max(maxLen, i - stack.peek());
}
}
}
return maxLen;
}
}
官方解法
另一种官方解法，和我自己的想法有点类似，就是不用栈，从左往右遍历，在left等于right的情况下，计算总数，在right大于left的情况下，清空left和right，接着计算。
然后从右往左进行计算，为啥要从右往左计算呢，因为在从左往右的过程中，如果有left大于right的情况，后面可能就翻不过来了如"(（）()"，这种一直不会相等，后面这4个有效的也算不出来，这种情况下，是left大于right的情况下清空重算。
public class Solution {
public int longestValidParentheses(String s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right >= left) {
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left >= right) {
left = right = 0;
}
}
return maxlength;
}
}
