首页 > 代码库 > 32. Longest Valid Parentheses

32. Longest Valid Parentheses

一、题目

  1、描述

    技术分享

  2、题意

    求满足括号闭合规则的最大子串长度

 

二、解答

  1、思路:

    刚开始想到的是前面的判断这个字符串是否满足闭合规则的方法,即建一个Stack,当为‘(‘ 时候,‘)‘ 入栈,当为 ‘)‘ 时候,判断栈顶是否为 ‘)’, 这种方法未解决 ()(() 这种情况。看到网上大神的方法,是记录每个字符的下标,让匹配的后面的‘)‘的下标减去前面起始的‘(’的下标,即为 跨度。

    public static int longestValidParentheses3(String s) {
        
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        int left = -1;
        
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ‘(‘)
                stack.push(i);    // 记录下标
            else {
                if(stack.isEmpty()) left = i;
                else {
                    stack.pop();
                    if(stack.isEmpty()) max = Math.max(max, i - left);
                    else                max = Math.max(max, i - stack.peek());
                }
            }
        }
        
        return max;
    }
    

 

  方法二: 优化

    public static int longestValidParentheses4(String s) {
        
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int result = 0;
        stack.push(-1);
        
        // i-stack.peek() == 有效长度
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ‘)‘ && stack.size() > 1 && s.charAt(stack.peek()) == ‘(‘) {
                stack.pop();
                result = Math.max(result, i-stack.peek());
            }
            else {
                stack.push(i);
            }
        }
        return result;
    }

 

32. Longest Valid Parentheses