欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode32——最长有效括号(栈)

程序员文章站 2022-07-12 23:41:03
...

题目描述

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

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”

示例 2:

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

题目分析

主要是采用栈的思想,通过表格来列出整个过程。idx是字符串数组的下标,leftmost初始值为-1,stack初始为空,max初始为0.

bracket idx leftmost stack max
0 -1 empty 0
( 0 -1 0 0
( 1 -1 0,1 0
) 2 -1 0 2-0
( 3 -1 0,3 2
) 4 -1 0 4-0
) 5 -1 empty 5-(-1)=6
( 6 -1 6 6-(-1)=7
) 7 -1 empty 7-(-1)=8
) 8 8 empty 8
( 9 8 9 9-8=1
) 10 8 empty 10-8=2

代码

Java代码如下:

class Solution {
    public int longestValidParentheses(String s) {
        if(s==null||s.length()<2) 
            return 0;
        int n=s.length();
        int max=0;
        int leftmost=-1;
        Stack<Integer> stack =new Stack<Integer>();
        for(int i=0;i<n;i++)
        {
            if(s.charAt(i)=='(')
            {
                stack.push(i);
            }
            else
            {
                if(stack.isEmpty())
                {
                    leftmost=i;
                }
                else
                {
                int j=stack.pop();
                if(stack.isEmpty())
                {
                    max=Math.max(max,i-leftmost);
                }
                else
                {
                    max=Math.max(max,i-stack.peek());
                }
                }
            }
        }
        return max;
    }
}