Leetcode32.最长有效括号

1.题目描述

给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

2.解法

暴力法

一看到这道题目,由于思维定式,因为以前做过一个有效符号问题,就是采用栈来进行符号的匹配,然后我就开始动手撸码了,而这道题目要求的最长的字串的长度,我直接就傻了,下面先来看一下暴力方法解决:

思路:

对当前字符串的每个偶数个字串执行isValid方法,在isValid()方法中使用一个栈来判断当前字串是否为有效的匹配

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push('(');
            } else if (!stack.empty() && stack.peek() == '(') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.empty();
    }
    public int longestValidParentheses(String s) {
        int maxlen = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 2; j <= s.length(); j+=2) {
                if (isValid(s.substring(i, j))) {
                    maxlen = Math.max(maxlen, j - i);
                }
            }
        }
        return maxlen;
    }
}

这种方法在理论上虽然是可以实现的,但是根本提交不上去,超出时间限制,需要进行改进


早上的时候一直都是将栈里面的元素设置为Character,但是由于求出字串比较复杂一直没有实现,期间也是想过是否可以将栈里面的元素设置为Integer,但是没有从这条路走,晚上看到题解的时候直接就明白了,后来,我总算学会了,如何去.....

public class Solution {

    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        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;
    }
}

首先将-1压栈,用来除了进行pop()操作之后栈为空的情况,如果入栈的符号为‘)’,那么先进行一次pop()操作,压入-1也可以避免空栈异常。这个方法实在是太妙了,栈顶元素保持的一直在有效最长字串的最小下标,后面可能会更换栈顶,但是一直使用maxans来维护这个最大值

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode32最长有效括号md