区块链技术博客
www.b2bchain.cn

32. 最长有效括号 栈或者遍历括号数目

这篇文章主要介绍了32. 最长有效括号 栈或者遍历括号数目,通过具体代码讲解8446并且分析了32. 最长有效括号 栈或者遍历括号数目的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了32. 最长有效括号 栈或者遍历括号数目。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8446.html。具体如下:

原文地址

32. 最长有效括号

这个地方开始括号”中间多加了一个空格。。。。 
法1:栈 时间O(n) 空间O(n)

  class Solution {     public int longestValidParentheses(String s) {         int ans=0;         //存储下标         Stack<Integer> stack=new Stack<>();         stack.push(-1);         for (int i = 0; i <s.length() ; i++) {             if(s.charAt(i)=='(') stack.push(i);             else{                 //此时把左括号或-1出栈                 stack.pop();                 //此时右括号入栈,表示没有左括号匹配                 if(stack.isEmpty()) stack.push(i);                 else ans=Math.max(ans,i-stack.peek());             }         }         return ans;     } }

法2:前后各遍历一次 时间O(n) 空间O(1)

 class Solution {     public int longestValidParentheses(String s) {         int ans=0;         int left=0,right=0;         for (int i = 0; i <s.length() ; i++) {              if(s.charAt(i)=='(') left++;             else right++;             //需要乘2             if(left==right) ans=Math.max(ans,right*2);             //右括号多,无法完成匹配             if(left<right){                 left=0;                 right=0;             }         }          //需要重新置为0开始操作         left=0;right=0;         for (int i = s.length()-1; i >=0 ; i--) {              if(s.charAt(i)=='(') left++;             else right++;             if(left==right) ans=Math.max(ans,right*2);             //左括号多,无法完成匹配             if(left>right){                 left=0;                 right=0;             }         }         return ans;     }

 

本文地址https://www.b2bchain.cn/8446.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 32. 最长有效括号 栈或者遍历括号数目
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们