LeetCode32. Longest Valid Parentheses

发表于 | 分类于 |

思考构思

首先针对括号匹配问题：借鉴LeetCode20那题的经验，我们可以想到借助栈，接下来就开始验证栈是否能解决该问题

思路一

  1. 考察第i位字符c
  2. 如果c为左括号，把位置坐标i压栈
  3. 如果c为右括号，对栈进行弹栈，得到index，i-index+1 就是匹配的长度

验证

  • 对于(())，算法有效
  • 对于输入()()，算法无效

需要针对第二种情况，重新构思

思路二

  1. 考察第i位字符c
  2. 如果c为左括号，把位置坐标i压栈
  3. 如果c为右括号，如果栈非空（匹配成功），对栈进行弹栈，访问弹栈后的栈顶元素index
    • 由该算法可知，此时栈顶元素(stack.peek())代表着是最右边不匹配位置，i到index之间的括号都是匹配的，即i-index 就是匹配的长度
  4. 如果c为右括号，栈为空（匹配失败）,或者栈顶元素所代表的字符不是’(‘ (匹配失败)，将i入栈

验证

  • 对于(())，算法有效
  • 对于(),算法错误，没有考虑边界问题

思路三

在思路二的第3步，在防卫stack.peek()时，需要先判断栈是否为空，如果为空，意味着从0到i都是匹配的，index代表最靠近i的一处不匹配位置，因此这里因设为-1

验证

  • 对于(())，算法有效
  • 对于()()，算法有效

思考边界值

  • s为空

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
	public int longestValidParentheses(String s) {
		if(s == null || s.length() == 0) return 0;
		
		Stack<Integer> stack = new Stack<>();

		stack.push(0);
		int len = 0;
		int front = 0;
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				stack.push(i);
			} else if (stack.isEmpty() || s.charAt(stack.peek()) != '(') {
				stack.push(i);
				
			} else {
                stack.pop();
				int index = -1;
				if(!stack.isEmpty()) {
					index = stack.peek();
				}
				len = Math.max(len, i - index );
			}
		}
		
		return len;
	}
}