网站中的横幅怎么做,百度云服务器安装wordpress,线上营销策划案例,减肥养生网站建设32. 最长有效括号
给你一个只包含 ( 和 ) 的字符串#xff0c;找出最长有效#xff08;格式正确且连续#xff09;括号
子串的长度。
示例 1#xff1a;
输入#xff1a;s (()
输出#xff1a;2
解释#xff1a;最长有效括号子串是 ()有事…32. 最长有效括号
给你一个只包含 ( 和 ) 的字符串找出最长有效格式正确且连续括号
子串的长度。
示例 1
输入s (()
输出2
解释最长有效括号子串是 ()
有事会暂停更新总之慢慢积累今天看一下这道题有动态规划、栈等解法本题采用计数器法思路就是分别定义两个计数器left和rigth首先从左向右遍历当遇到左括号时left遇到右括号时right当left right时记录此时有效子串的长度maxLength当right left时重置left和right为0遍历结束后不一定能得到最长有效括号的长度因为如果输入的是“((((((()”时此时如果从左向右遍历maxLength依旧为0我们需要从右向左遍历需要改变的条件是当left right时重置left和right为0两次不同方向遍历结束后就可以得到maxLength了时间复杂度为On,空间复杂度为O1代码如下
class Solution {public int longestValidParentheses(String s) {int left 0, right 0, maxLength 0;// 从左向右遍历for (int i 0; i s.length(); i) {if (s.charAt(i) () {left;} else {right;}if (left right) {maxLength Math.max(maxLength, right * 2);} else if (right left) {left right 0;}}left right 0;// 从右向左遍历for (int i s.length() - 1; i 0; i--) {if (s.charAt(i) )) {right;} else {left;}if (left right) {maxLength Math.max(maxLength, left * 2);} else if (left right) {left right 0;}}return maxLength;}
}
题目链接题单 - 力扣LeetCode全球极客挚爱的技术成长平台
