32

题目

暴力破解法试了半天，没破解出来，估计破解出来也会超时。这一题真的难

方法一：使用动态规划来解决，具体怎么解决还是看leetcode官方视频吧。

var longestValidParentheses = function(s) {
  let arr = new Array(s.length).fill(0);
  let max = 0;
  for(let i=0;i<s.length;i++){
    //为右括号，判断前一个值是否存在，如果存在判断数值
    if(s[i]===")"){
      if(i!==0&&s[i-arr[i-1]-1]==="("){
        arr[i] = arr[i-1] + 2;
        if(i-arr[i-1]-2>=0)arr[i]+=arr[i-arr[i-1]-2];
        max = Math.max(max,arr[i]);
      }
    }
  }
  return max;
};

方法二：栈

var longestValidParentheses = function(s) {
  let stack = [-1];
  let length = 0;
  let max = 0;
  for(let i=0;i<s.length;i++){
    if(s[i]==="("){
      stack.push(i);
    }else{
      stack.pop();
      if(stack.length===0){
        stack.push(i);
      }else{
        length = i-stack[stack.length-1];
        max = Math.max(length,max);
      }
    }
  }
  return max;
};