32. 最长有效括号
对于遇到的每个 ‘(’ ，将它的下标放入栈中。 对于遇到的每个‘)’ ，弹出栈顶的元素并将当前元素的下标与弹出元素下标作差，得出当前有效括号字符串的长度。通过这种方法，继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。
public class Solution {
public int longestValidParentheses(String s) {
//最长字串计数
int maxans = 0;
//创建栈
Stack<Integer> stack = new Stack<>();
//首先将-1压入栈中
//1# 不加 -1的话。碰见类似 "()" 这种情况，在碰到右括号后直接弹出左括号 此时判断 stack=empty 会做压栈操作。
//maxans = Math.max(maxans, i - stack.peek()); 这句话不会执行。
//2# 加入当前右括号是为了作为下次 i - stack.peek() 而使用的。
stack.push(-1);
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 {
//计算最大值
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
}
复杂度分析
时间复杂度： O(n) 。 n 是给定字符串的长度。
空间复杂度： O(n) 。栈的大小最大达到 n 。
利用栈结构进行符号的匹配
