提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  数据库

当前栏目

32. 最长有效括号

索引
2023-04-18 16:11:32 时间

思路：

  • 栈的功能：栈存储索引。在遍历过程中，只要有两个连续索引对应字符可以构成一对括号就出栈，这样栈中存储的都是到当前位置暂时不可以构成括号的索引。
  • 排除构不成括号的情况
    • i. 当前栈为空。当前字符s[i]将会是栈中第一个字符，无法跟之前的字符构成一对括号
    • ii. 当前字符s[i]是左括号'('。左括号无法跟栈顶元素构成一对括号
    • iii. 栈顶元素是右括号')'。无论当前字符s[i]是什么，都无法和栈顶元素构成一对括号 其实也就是栈顶元素必须为'('，当前字符s[i]必须为')'，这样才能构成一对括号
  • 构成一对括号以后，栈顶元素出栈。
  • 当前有效括号的长度 = 当前索引i - 栈顶存储的索引stack[-1] 最后要返回的最长有效括号长度即为res = max(res, i - stack[-1]) 因为此时栈可能为空，如果为空就是前面的元素都是括号，那么res = max(res, i - (-1))

代码：

 public int longestValidParentheses(String s) {
        LinkedList<Integer> stack =new LinkedList<>();
        int res=0;
        for (int i = 0; i < s.length(); i++) {
            //如果当前字符是绝对不能匹配成功的，进行压栈
            if (stack.isEmpty()||s.charAt(i)=='('||s.charAt(stack.getLast())==')'){
                stack.add(i);
            }else {
                stack.removeLast();
                res=Math.max(res,stack.isEmpty()?i+1:i-stack.getLast());
            }
        }
        return res;
    }

相关文章