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

32. Longest Valid Parentheses

2024-10-12 07:48:02   213人阅读

一、题目

　　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


联系
我们