自己解法
看到这题的第一想法就是他喵的括号又见括号,之前括号有效性的精髓就是左括号个数要大于右括号个数,所以第一想法是,遇到左括号加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;
}
}