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

原文地址

https://www.b2bchain.cn/5838.html

这个地方开始括号''中间多加了一个空格。。。。  法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;     }