[LeetCode][JavaScript]Longest Valid Parentheses

浏览数：112 / 时间：2015年06月08日

https://leetcode.com/problems/longest-valid-parentheses/

Longest Valid Parentheses

Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

没用动态规划，就用了个栈...

举个栗子：)(()())(

技术分享

栈里的数字就是weight啦，用个栈一顿倒来倒去之后，就变成了一个数列。

就好像这样-1 2 10 8 2 -1 12 8 -1 2 4

问题就转换成了合并数列中的正数，最大的就是结果。

啊啊啊，这样解好麻烦，写了好多行，好伤心，老老实实dp就好了嘛。

 1 /**
 2  * @param {string} s
 3  * @return {number}
 4  */
 5 var longestValidParentheses = function(s) { 
 6     var stack = [];
 7     for(var i = 0; i < s.length; i++){
 8         if(s[i] === ‘(‘){
 9             stack.push({
10                 value : ‘(‘,
11                 weight : -1
12             });
13         }else{
14             var targetIndex = -1;
15             for(var j = stack.length - 1; j >= 0; j--){
16                 if(stack[j].value === ‘(‘){
17                     targetIndex = j;
18                     break;
19                 }
20             }
21             
22             if(targetIndex === -1){
23                 stack.push({
24                     value : ‘)‘,
25                     weight : -1
26                 });
27             }else{
28                 var merge = null;
29                 while(stack.length - targetIndex - 1){
30                     var tmp = stack.pop();
31                     if(merge === null){
32                         merge = tmp;
33                     }else{
34                         merge.value += tmp.value;
35                         merge.weight += tmp.weight;
36                     }
37                 }
38                 stack.pop();
39                 if(merge === null){
40                     stack.push({
41                         value : ‘()‘,
42                         weight : 2
43                     });
44                 }else{
45                     stack.push({
46                         value : "(" + merge.value + ")",
47                         weight : merge.weight + 2
48                     });
49                 }
50             }
51         }
52     }
53     
54     var max = 0;
55     var currMax = 0;
56     for(i = 0; i < stack.length; i++){
57         var curr = stack[i];
58         if(curr.weight === -1){
59             if(currMax > max){
60                 max = currMax;
61             }
62             currMax = 0;
63         }else{
64             currMax += curr.weight;
65         }    
66     }
67     if(currMax > max){
68         max = currMax;
69     }
70     return max;
71 };