IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【LeetCode】Day130-最长有效括号 -> 正文阅读

[数据结构与算法]【LeetCode】Day130-最长有效括号

题目

32. 最长有效括号【困难】

题解

括号问题的标答,用栈解决,但是如果用传统做法,挨个测试字符串的子串是否有效时间复杂度会达到 O ( n 3 ) O(n^3) O(n3),通过不了所有测试用例,于是这道题改了栈的用法,始终保持栈底元素为已遍历元素中最后一个没匹配的右括号下标,但是如果字符串首个字符是‘(’,那么就不满足该条件,因此一开始入栈“-1”元素以保持统一

这道题的具体做法是:

  • 遇到 ‘(’,下标入栈
  • 遇到 ‘)’,栈顶元素先出栈,表示匹配了当前右括号,这时:
    如果栈空,右括号下标入栈
    如果栈不空,右括号下标-栈顶元素(剩余的不能匹配的)=以该右括号为结尾的最长有效括号长度

从前往后遍历字符串并更新答案即可

class Solution {
    public int longestValidParentheses(String s) {
        int n=s.length(),res=0;
        if(n<2)
            return 0;
        Stack<Integer>stack=new Stack<>();
        stack.push(-1);
        for(int i=0;i<n;i++){
            if(s.charAt(i)=='(')
                stack.push(i);
            else{
                stack.pop();
                if(!stack.empty())
                    //当前全部人数减去剩余无法配对的人数(单身)即res
                    res=Math.max(res,i-stack.peek());
                else   
                    stack.push(i);
            }
        }
        return res;
    }
}

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( n ) O(n) O(n)

动态规划

困难题怎么能少得了动态规划呢

  1. 状态定义:dp[i]以下标 i 字符结尾的最长有效括号的长度。
  2. 状态转移方程
  • 1)s[i]==‘)’ 并且 s[i-1]==‘(’:…()
    dp[i]=dp[i-2]+2
  • 2)s[i]==‘)’ 并且 s[i-1]==‘)’:…))
    s[i-dp[i-1]-1]==‘(’:dp[i]=dp[i-1] + dp[i-dp[i-1]-1] + 2
    如果倒数第二个")“是有效括号sub的一部分,对于最后一个”)",如果他是更长子串的一部分,则一定有一个对应的左括号。因此,如果sub前面刚好是一个左括号,就用2加上dp[i-1](即sub的长度)更新dp[i],然后sub之前的有效子串的长度也要加上,即dp[i-dp[i-1]-2]
    在这里插入图片描述
  1. 初始条件:dp[i]=0
  2. 返回值:max(dp[i])
class Solution {
    public int longestValidParentheses(String s) {
        int n=s.length(),res=0;
        if(n<2)
            return 0;
        int[] dp=new int[n];
        for(int i=1;i<n;i++){
            if(s.charAt(i)==')'){
                //"()"
                if(s.charAt(i-1)=='(')
                    dp[i]=i-2>=0?dp[i-2]+2:2;
                //"))"
                else if(s.charAt(i-1)==')'){
                    //"(...))"
                    if(i-dp[i-1]-1>=0&&s.charAt(i-dp[i-1]-1)=='(')
                        dp[i]=dp[i-1]+2+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0);
                }
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( n ) O(n) O(n)

正向逆向结合法(不需要额外空间)

很巧妙的方法,需要遍历字符串两遍

  1. 从左向右遍历
    遇到“(”,left++;遇到“)”,right++;
    如果left==right,计算当前有效括号长度,并更新最长的;
    如果right>left,双方清零
  2. 从右向左遍历
    前两条类比相同
    如果left>right,双方清零。这样是为了避免漏掉左括号始终比右括号多的情况,如(()
class Solution {
    public int longestValidParentheses(String s) {
        int n=s.length(),res=0,left=0,right=0;
        if(n<2)
            return 0;
        //从左向右遍历
        for(int i=0;i<n;i++){
            if(s.charAt(i)=='(')
                left++;
            else
                right++;
            
            if(left==right)
                res=Math.max(res,left+right);
            if(right>left){
                left=0;
                right=0;
            }
        }
        left=right=0;
        //从右向左遍历
        for(int i=n-1;i>=0;i--){
            if(s.charAt(i)=='(')
                left++;
            else
                right++;
            if(left==right)
                res=Math.max(res,left+right);
            if(left>right){
                left=0;
                right=0;
            }
        }
        return res;
    }
}

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( 1 ) O(1) O(1)

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-15 02:14:52  更:2022-09-15 02:15:16 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 18:38:19-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计