当前位置:网站首页>每日一题-最长有效括号-0724
每日一题-最长有效括号-0724
2022-08-05 05:17:00 【菜鸡程序媛】
题目
给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
思路
- 括号匹配题目优先从栈的角度切入,本题中需要找到最长的括号子串的长度,通过数组的下标进行匹配
- 优先入栈一个-1的下标,作为栈底的元素(保证栈不会空)
- 遇到左括号的时候入栈,右括号的时候先弹出当前的栈顶元素,如果这个时候栈非空,证明之前入栈过左括号,满足括号对的前提要求;如果是空的,右括号的下标入栈,保证栈不会是空的,还有一点就是后面有满足要求的括号对的时候,作为栈顶下标元素计算当前子串的长度
- 最后通过sum不断迭代,更新当前的最大值
代码
class Solution {
public int longestValidParentheses(String s) {
if(s == null || s.length() <= 0)
return 0;
Stack<Integer> stack = new Stack<>();
int sum = 0;
//站岗
stack.push(-1);
for(int i = 0; i < s.length(); i ++){
if(s.charAt(i) == '('){
stack.push(i);
}else{
stack.pop();
if(stack.isEmpty()){
stack.push(i);
}else{
sum = Math.max(sum, i - stack.peek());
}
}
}
return sum;
}
}
边栏推荐
猜你喜欢
C语言入门笔记 —— 函数(1)
【nodejs】第一章:nodejs架构
【22李宏毅机器学习】课程大纲概述
伪RTOS-ProroThread在CH573芯片上的移植
栈区中越界可能造成的死循环可能
ECCV2022 | RU&谷歌提出用CLIP进行zero-shot目标检测!
数控直流电源
leetCode刷题之第31题
CH32V307 LwIP移植使用
[Pytorch study notes] 9. How to evaluate the classification results of the classifier - using confusion matrix, F1-score, ROC curve, PR curve, etc. (taking Softmax binary classification as an example)
随机推荐
ECCV2022 | RU & Google propose zero-shot object detection with CLIP!
LeetCode刷题之第416题
栈的应用——力扣 20.有效的括号
《基于机器视觉测量系统的工业在线检测研究》论文笔记
[Pytorch study notes] 9. How to evaluate the classification results of the classifier - using confusion matrix, F1-score, ROC curve, PR curve, etc. (taking Softmax binary classification as an example)
Redis集群(docker版)——从原理到实战超详细
MySQL主从复制—有手就能学会的MySQL集群搭建教程
LeetCode刷题之第1024题
[Database and SQL study notes] 10. (T-SQL language) functions, stored procedures, triggers
PoE视频监控解决方案
网管日记:故障网络交换机快速替换方法
leetCode刷题之第31题
LeetCode刷题之第33题
【ts】typeScript高阶:any和unknown
【nodejs】第一章:nodejs架构
多边形等分
TinyFlashDB:一种超轻量的可纠错的通用单片机flash存储方案
SharedPreferences and SQlite database
LeetCode刷题之第530题
电子产品量产工具(4)-UI系统实现