leetcode-longest-valid-parentheses

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/longest-valid-parentheses/

　　给你一个字符串只含(和)，求出这个字符串的所有满足正确括号匹配原则的子串的最大子串长度。

题目分析

　　最开始自己拿栈实现，没有写对，隐约觉得O(n)可以实现，看了一下geeksforgeeks上的正确解法。确实用栈O(n)实现。思路是这样：

  1. 初始化栈，栈中放入-1作为辅助
  2. 从左向右扫描字符串：
    1. 遇到(时，将index压栈
    2. 遇到)时，先弹栈（大部分情况弹出的是匹配的左括号），如果此时栈为空，那么说明当前这次没有产生符合条件的子串（因为把上次的base值都已经弹出了），那么将index压栈作为下次的base（相当于更新一下base值，为了下次计算子串长度的）。如果栈不为空，那么这次产生了符合条件的子串，当前的index减去栈顶元素的值(栈中保存的是下次匹配字符串的base，用来求长度的)，用它更新max。
    3. 直到全部扫描完，就能得到结果。具体过程可能描述的还不够清晰，看代码理解一下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        char[] c = s.toCharArray();
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(-1);
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if (c[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    ans = Math.max(ans, i - stack.peek());
                }
            }
        }
        return ans;
    }
}

　　复杂度：O(n)