我的朋友在一次采访中遇到一个问题，他被告知有O(n)解决方案.但是，我们两个都没有想过.这是问题:
My friend ran into a question in an interview and he was told that there is an O(n) solution. However, neither of us can think it up. Here is the question:
有一个仅包含(和)的字符串，查找最长有效括号子字符串的长度，该字符串应格式正确.
There is a string which contains just ( and ), find the length of the longest valid parentheses substring, which should be well formed.
例如)()())" ，最长的有效括号是()()，长度为4.
For example ")()())", the longest valid parentheses is ()() and the length is 4.
我通过动态编程解决了这个问题，但不是O(n).有什么想法吗?
I figured it out with dynamic programming, but it is not O(n). Any ideas?
public int getLongestLen(String s) { if (s == null || s.length() == 0) return 0; int len = s.length(), maxLen = 0; boolean[][] isValid = new boolean[len][len]; for (int l = 2; l < len; l *= 2) for (int start = 0; start <= len - l; start++) { if ((s.charAt(start) == '(' && s.charAt(start + l - 1) == ')') && (l == 2 || isValid[start+1][start+l-2])) { isValid[start][start+l-1] = true; maxLen = Math.max(maxLen, l); } } return maxLen; } 推荐答案我之前曾做过这个问题，在压力下提出O(n)解决方案并不容易.就是这个，这是通过堆栈解决的.
I did this question before, and it is not easy to come up with O(n) solution under pressure. Here is it, which is solved with stack.
private int getLongestLenByStack(String s) { //use last to store the last matched index int len = s.length(), maxLen = 0, last = -1; if (len == 0 || len == 1) return 0; //use this stack to store the index of '(' Stack<Integer> stack = new Stack<Integer>(); for (int i = 0; i < len; i++) { if (s.charAt(i) == '(') stack.push(i); else { //if stack is empty, it means that we already found a complete valid combo //update the last index. if (stack.isEmpty()) { last = i; } else { stack.pop(); //found a complete valid combo and calculate max length if (stack.isEmpty()) maxLen = Math.max(maxLen, i - last); else //calculate current max length maxLen = Math.max(maxLen, i - stack.peek()); } } } return maxLen; }