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;
}
}
上一篇: LeetCode每日一题
推荐阅读
-
荐 【小白用python刷Leetcode】32. 最长有效括号
-
32. 最长有效括号 动态规划
-
LeetCode-32.Longest Valid Parentheses最长有效括号子串
-
括号相关题目 LeetCode 20 有效括号 LeetCode 32 最长有效括号子串
-
括号字符串的有效性和最长有效长度
-
括号字符串的有效性和最长有效长度
-
Longest Valid Parentheses leetcode java (求最长有效匹配括号子串的长度)-动态规划
-
【leetcode】32 最长有效括号(动态规划,栈)
-
栈-LeetCode32-最长有效括号
-
LeetCode32——最长有效括号(栈)