32. 最长有效括号

栈

import java.util.Stack;
class Solution {
  // 最长字串 而非符合的有效括号

  // 一开始是通过匹配()())( 有多少对是满足条件的
      //出现问题 如何去识别哪段子串是最长 没法确定 因为算到最后是整个括号字符串有多少个匹配
      //( 左括号 容易卡在栈里面 可能到最后还没能pop出来
  //解决方案
      //https://www.bilibili.com/video/av66667898/
      //栈不再是保存字符了 而是保存下标 代码如下
  public int longestValidParentheses(String s) {
      char c[] = s.toCharArray();
      int n = c.length;
      int ans = 0;
      int count = 0;
      Stack<Integer> stack = new Stack<Integer>();
      stack.add(-1);
      for (int i = 0; i < n; i++) {
          if (c[i] == '(') {
              stack.add(i);
          }
          else {
              stack.pop();
              if(stack.size()==0)stack.add(i);
              else {
                  count  = i - stack.peek();//不用pop出来 留给下一轮再pop
              }
              ans = Math.max(count,ans);
          }
      }
      return ans ;
  }
}

大雪菜的解法

//y总的解法
  // 括号序列合法 <==> 前缀和 >= 0 且 总和等于0
  // start 枚举的这一段的开头
  // cnt 前缀和
  // 1. cnt < 0 -> start = i , cnt = 0;
  // 2. cnt > 0 -> 继续做
  // 3. cnt == 0 -> [start , i]是一段合法的括号序列
  public int work(char c[]) {
      int start = 0;
      int cnt = 0;
      int ans = 0;
      for (int i = 0; i < c.length; i++) {
          if (c[i] == '(')
              cnt++;
          else {
              cnt--;
              if (cnt < 0) {
                  start = i + 1;
                  cnt = 0;
              }
              else if(cnt==0)ans = Math.max(ans, i - start + 1);
          }
      }
      return ans;
  }

  public int longestValidParentheses(String s) {
      char c[] = s.toCharArray();
      int res = work(c);
      char c1[] = s.toCharArray();
      for(int i = 0; i < c.length ; i++) {
          c1[i] = c[c.length-1-i];
          c1[i]^=1;
      }

      return Math.max(res, work(c1));
  }
}