LongestValidParentheses [source code]
public class LongestValidParentheses {
static
/******************************************************************************/
class Solution {
public int longestValidParentheses(String s) {
char[] chs = s.toCharArray ();
int[] dp = new int[chs.length];
int max = 0;
for (int i = 1; i < chs.length; i++) {
if (chs[i] == ')') {
if (chs[i - 1] == '(')
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
else if (i - dp[i - 1] - 1 >= 0 && chs[i - dp[i - 1] - 1] == '(')
dp[i] = 2 + dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
}
max = Math.max (max, dp[i]);
}
return max;
}
}
/******************************************************************************/
public static void main(String[] args) {
LongestValidParentheses.Solution tester = new LongestValidParentheses.Solution();
}
}
关于DP我们其实前面已经总结过很多次了, 比如怎么定义表格, 维度, entry; 这里给一个新的点子, 在很多问题当中, 刚开始完全没有思路, 但是类似这题, 知道用DP做的时候(搜索题, DP不是新鲜事), 可以尝试, 比如给的)()()), 从左到右, 一点一点的看, 看这个input逐渐增加的过程当中, 每一个位置, 你认为结果应该是什么? 然后来分析root level decision之类的信息, 或者你需要什么信息才能完成这个decision; input的size, 在DP问题当中是至关重要的;
稍微想了一会儿, 好像一点思路都没有; 不准备继续浪费时间了;
发现一个小问题, 之前认为可以用Arrays.deepToString来进行一个对array的print的debug; 结果发现一个很奇葩的问题:
java> Arrays.deepToString(new int[][]{{1,2,3}, {4,5,0}});
java.lang.String res29 = "[[1, 2, 3], [4, 5, 0]]"
java> Arrays.deepToString (new int[] {1,2,3})
ERROR: incompatible types: int[] cannot be converted to java.lang.Object[]
Arrays.deepToString (new int[] {1,2,3});
^
原来一维的array跟matrix的实现方式是不一样的, 高维度的array其实底下还是用object来偷偷实现的. 那么我们想要print一维array的时候怎么办? 看下面这个小窍门就行了;
java> Arrays.deepToString (new int[][] {ar1})
java.lang.String res30 = "[[1, 2, 3]]"
int[][]其实就是一个[] of Object本身;
最后写的是这个DP的解法, 速度是16ms (98%), 还算好;
editorial
Approach #1 Brute Force [Time Limit Exceeded]
Algorithm
In this approach, we consider every possible non-empty even length substring from the given string and check whether it's a valid string of parentheses or not. In order to check the validity, we use the Stack's Method.
Every time we encounter a
‘(’, we push it onto the stack. For every
‘)’ encountered, we pop a
‘(’ from the stack. If
‘(’ isn't available on the stack for popping at anytime or if stack contains some elements after processing complete substring, the substring of parentheses is invalid. In this way, we repeat the process for every possible substring and we keep on storing the length of the longest valid string found so far.
Example:
"((())"
(( --> invalid
(( --> invalid
() --> valid, length=2
)) --> invalid
((()--> invalid
(())--> valid, length=4
maxlength=4
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push('(');
} else if (!stack.empty() && stack.peek() == '(') {
stack.pop();
} else {
return false;
}
}
return stack.empty();
}
public int longestValidParentheses(String s) {
int maxlen = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 2; j <= s.length(); j+=2) {
if (isValid(s.substring(i, j))) {
maxlen = Math.max(maxlen, j - i);
}
}
}
return maxlen;
}
}
还是比较直接的, N^3的复杂度;
Approach #2 Using Dynamic Programming [Accepted]
We make use of a
dp array where
ith element of
dp represents the length of the longest valid substring ending at
ith index.
public class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
int dp[] = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
}
网页有解释, 总体来说是一个比较复杂的题目; 一般来说, 难一点的DP题目, 是root involvement比较难找; 这个题目这里就看出来DP解法的难度了. 不过这里实际上表格和entry的定义并不复杂, 而且表格也只有一维的; 感觉我还是没有去思考, 其实我在刚才grow input size的实验的过程当中大概有点找到这个节奏了, 不过没有总结出来; 总体来说这个算法真的就是非常的直白而且聪明;
Approach #3 Using Stack [Accepted]
Algorithm
Instead of finding every possible string and checking its validity, we can make use of stack while scanning the given string to check if the string scanned so far is valid, and also the length of the longest valid string. In order to do so, we start by pushing
−1 onto the stack.
For every
‘(’ encountered, we push its index onto the stack.
For every
‘)’ encountered, we pop the topmost element and subtract the current element's index from the top element of the stack, which gives the length of the currently encountered valid string of parentheses. If while popping the element, the stack becomes empty, we push the current element's index onto the stack. In this way, we keep on calculating the lengths of the valid substrings, and return the length of the longest valid string at the end.
public class Solution {
public int longestValidParentheses(String s) {
int maxans = 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 {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
}
网页上有一个例子, 看他这里的解释的其实很模糊, 估计就是照着代码说了一遍;
这个其实就有点像是一个2sum一样的算法, 但是没有那个那么复杂; 他这里这个sentinel的作用其实没有那么重要, 只是为了让判断Empty更加方便; 你考虑())())这个例子, 最后两个右括号发生了什么; 大概就能理解这个算法的意思了; 一旦当我们发现pop出来的是sentinel, 我们就直接认定当前这次配对是失败的, 往往原因就是因为redundant right parens. 这个时候就把这个多余的右括号直接扔进去, 当新的sentinel, 你可以考虑当有)))..这样的东西的时候, 发生的是什么: 多个连续的多余右括号是没有关系的, the only one that matters is the rightmost one.
这个算法看起来确实很简单, 几乎不像是一个hard的算法, 但是能够写出这个算法来, 实际上是不简单的; 这个算法需要你准确的认识到, 到底是什么导致了了一个substring会invalid; 这里这个算法的作者就是认识到, 真正让一个substring被中断的原因, 就是因为出现了多余的右括号. 当然这个时候你看过这个答案的时候, 肯定觉得这个太简单了, 当然是这样啊, 但是实际上当你自己想的时候, 这个insight并不是那么容易就能想出来的;
总体来说这个算法还是非常的精确到位, 而且当你真正理解了关键的insight之后, 可能觉得比上面那个DP还要简单; 不过这个insight本身其实才是最难的部分; 这个题目的难点其实就是分析题目本身; 而理解题目本身的本质就是很难, 这也是为什么这题被认为是hard, 这也是为什么我自己写的时候, 连想出来一个人逻辑都做不到;
Approach #4 Without extra space [Accepted]
Algorithm
In this approach, we make use of two counters
left and
right. First, we start traversing the string from the left towards the right and for every
‘(’ encountered, we increment the
left counter and for every
‘)’ encountered, we increment the
right counter. Whenever
left becomes equal to
right, we calculate the length of the current valid string and keep track of maximum length substring found so far. If
right becomes greater than
left we reset
left and
right to 0.
Next, we start traversing the string from right to left and similar procedure is applied.
这个就是一个简单的2pointer的做法, 严格来说这个算法都不能说是一个sliding window的算法, 因为counts的处理非常的简单; 而且这里的这个insight你也看的出来, 就是看出来, 这题的关键就是关注redundant right parens.
public class Solution {
public int longestValidParentheses(String s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right >= left) {
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left >= right) {
left = right = 0;
}
}
return maxlength;
}
}
注意他这里的window也是从Empty开始的, 这个我们之前做题的时候已经总结过一次了;
这里他这俄格算法为什么要从左右两边各自来一次? 有没有什么justification? 还是就是用test给break出来的? 因为从本质上来说, 我感觉这个算法跟上面的第三个做法是非常类似的, 为什么#3不需要左右两遍, 而#4就需要了?
干脆自己提交了一个例子试试, 然后(()这个例子, 如果只做第一个pass, 那么我们会返回0; 然后再仔细回头看代码, 发现这里这个写法判断的实际上是left == right.
这个帖子里面有#4的另外一种写法:
private int findValidParentheses(String s, int start, int end, int step, char cc) {
int maxLen = 0, count = 0, len = 0;
for (int i=start; i!=end; i+=step) {
if (s.charAt(i)==cc) {
++count;
} else {
if (count>0) {
// exist a matching
--count;
len += 2;
if (count==0) maxLen = Math.max(maxLen, len);
} else {
// no matching
len = 0;
}
}
}
return maxLen;
}
public int longestValidParentheses(String s) {
return Math.max(findValidParentheses(s, 0, s.length(), 1, '('),
findValidParentheses(s, s.length()-1, -1, -1, ')'));
}
写法稍微有点区别; 不过这个帖子对于为什么需要走两遍, 其实也没有给很好的一个解释;
仔细看了一下上面这两种写法, 都是抓住了一个关键, 就是左括号的count跟右括号的count相等的时候, 才更新, 而不是说左边比右边多就可以更新; 我看完这个的第一想法就是凭什么不能直接多的时候就更新呢? 我就想写了这个算法:
public class Solution {
public int longestValidParentheses(String s) {
int left = 0, right = 0, maxlength = 0, prev_len = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max (maxlength, prev_len + 2 * right);
prev_len = 2 * right;
left = 0;
right = 0;
} else if (left < right) {
prev_len = 0;
left = 0;
right = 0;
} else {
maxlength = Math.max (maxlength, 2 * right);
}
}
return maxlength;
}
}
但是这个算法很轻松的就被"(()(((()"给break掉了:
i:(0), char:(, left:(1), right:(0), prev:(0), max:(0)
i:(1), char:(, left:(2), right:(0), prev:(0), max:(0)
i:(2), char:), left:(2), right:(1), prev:(0), max:(0)
i:(3), char:(, left:(3), right:(1), prev:(0), max:(2)
i:(4), char:(, left:(4), right:(1), prev:(0), max:(2)
i:(5), char:(, left:(5), right:(1), prev:(0), max:(2)
i:(6), char:(, left:(6), right:(1), prev:(0), max:(2)
i:(7), char:), left:(6), right:(2), prev:(0), max:(2)
所以最保险的还是在相等的时候进行更新, 因为相等的时候才是正确的balanced的定义; 但是相等的就有一个问题, 假如类似(()这样的, 最终也没有触发过相等, 那么就有问题了. 因为对称性, 一个简单的解决办法就是左右各来一遍.
那么为什么#3没有这个问题? 因为#3里面的Stack是记录index的, 所以在#3里面可以放肆的, 只要看到任何的匹配, 就直接更新max, 反正用的是index, 没毛病; 话说回来, stack of index, 这个东西感觉一旦出现的算法, 都不是什么好写的算法;
如果真正面试的时候, 碰到这种题目, 真的就是非常姜了;
看下来DP算法其实是感觉最聪明技术含量最高的. 后面两种做法虽然看起来犀利, 不过要求的前期理解太多了;
@cjxxm said in My O(n) solution using a stack:
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length(), longest = 0;
stack<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == '(') st.push(i);
else {
if (!st.empty()) {
if (s[st.top()] == '(') st.pop();
else st.push(i);
}
else st.push(i);
}
}
if (st.empty()) longest = n;
else {
int a = n, b = 0;
while (!st.empty()) {
b = st.top(); st.pop();
longest = max(longest, a-b-1);
a = b;
}
longest = max(longest, a);
}
return longest;
}
};
The workflow of the solution is as below.
- Scan the string from beginning to end.
- If current character is '(',
push its index to the stack. If current character is ')' and the
character at the index of the top of stack is '(', we just find a
matching pair so pop from the stack. Otherwise, we push the index of
')' to the stack.- After the scan is done, the stack will only
contain the indices of characters which cannot be matched. Then
let's use the opposite side - substring between adjacent indices
should be valid parentheses.- If the stack is empty, the whole input
string is valid. Otherwise, we can scan the stack to get longest
valid substring as described in step 3.
这个算法的观察力就格外的犀利了, 大概比算了一下, 还真的是这么一回事. 他的观察就是, 所有的unmatched parens之间的间隔的最大值, 就是我们最后要找的. 这些间隔有些甚至可能是0, 但是无所谓, 不关我们的事. 注意他第二个pass做这个处理的时候, 还偷偷的加了0和n这两个位置, 这个也是一个很犀利的处理; 总体来说这个算法真的是非常的浑然天成;
@dennyrong said in My O(n) solution using a stack:
This is my DP solution, just one pass
V[i] represents number of valid parentheses matches from S[j to i] (j<i)
V[i] = V[i-1] + 2 + previous matches V[i- (V[i-1] + 2) ] if S[i] = ')' and '(' count > 0
public int longestValidParentheses(String s) {
char[] S = s.toCharArray();
int[] V = new int[S.length];
int open = 0;
int max = 0;
for (int i=0; i<S.length; i++) {
if (S[i] == '(') open++;
if (S[i] == ')' && open > 0) {
// matches found
V[i] = 2+ V[i-1];
// add matches from previous
if(i-V[i]>0)
V[i] += V[i-V[i]];
open--;
}
if (V[i] > max) max = V[i];
}
return max;
}
这个跟editorial3是一样的做法, 不过editorial3比他的这个更加精简: 当我们碰到)的时候, 不用通过维护open来判断是否可以+2, 直接向前走一位看看是否至少有一个(就可以了.
妈的这题答案越看越感觉是智力题了;
这个是对原来的OP的解法的一个改良:
@vcoderld said in My O(n) solution using a stack:
Thanks for your answer. In fact, we don't have to get the maximum length after the first scan. Instead, we can get it dynamically while push and pop, which makes the run time get better. Following is my code.
public class Solution {
public int longestValidParentheses(String s) {
int max = Integer.MIN_VALUE;
s += "x";
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == ')' && !stack.empty() && s.charAt(stack.peek())== '(')
stack.pop();
else{
if(stack.empty()){
max = Math.max(max, i);
}
else
max = Math.max(max, i-stack.peek()-1);
stack.push(i);
}
}
return stack.empty() ? s.length() : max;
}
}
感觉他这样改了之后, 其实调用max的次数增加了, 比如(())这个东西, 现在你在[1]这个(的时候, 其实也调用了max, 但是如果按照OP原来的做法, 是没有必要的. 虽然减少了一个pass, 但是增加了一些compare操作; 最后理论上能够加速实际上还有待商榷, 当然, 如果OJ真的显示加速了, 我认为实际上也不能代表什么;
注意他用x这个sentinel来模拟OP原来的n的作用;
@Hockyuan said in My O(n) solution using a stack:
Thank you for your cool answer. I get a one-pass answer based on your answer.
int longestValidParentheses(string s) {
int size = s.size(), res = 0;
if(size < 2) return res;
stack<int> si;
for(int i = 0; i < size; ++i) {
if('(' == s[i]) si.push(i);
else {
if(si.empty()) si.push(i);
else {
if(s[si.top()] == '(') {
si.pop();
res = max(i - (si.empty()? -1: si.top()), res);
}
else si.push(i);
}
}
}
return res;
}
这个其实就跟editorial3的解法非常的类似了; 区别在于, 这个解法把所有的unmatched的都始终维护在Stack里面, 但是editorial3里面, 只维护the last seen unmatched parens.
@snap_dragon said in My O(n) solution using a stack:
A less tricky and straight forward version. Just mark the positions where the braces are valid and then calculate the longest valid...
public int longestValidParentheses(String s) {
boolean valid[] = new boolean[s.length()];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') stack.push(i);
else if (!stack.isEmpty()) {
valid[stack.pop()] = valid[i] = true;
}
}
return longest(valid);
}
private int longest(boolean[] valid) {
int max = 0;
int len = 0;
for (boolean v : valid) {
max = max(max, len = v ? len + 1 : 0);
}
return max;
}
非常简单明快的一个思路, 这个也是对题目的观察理解够透彻, 发现实际上给你一个string, 最后真正那些地方构成一个balanced的substring, 是固定的, 所以直接标记出来就行了; 他这个longest函数写的还是比较简明的; 上面的主函数里面, 一个思路就是左括号实际上始终是处于一个等待的状态, 只有足够的matching右括号出现之后, 才能够让之前等待的左括号被标记;
总体来说这个算法就是比较简单, 然后按理我也应该是能想出来的; 关键还是题目本身理解的不够努力; 而且看到是hard, 所以就很害怕, 实际上这个算法真的就是一个有想法之后非常好写;
这个好像就是editorial2的原型:
@jerryrcwong said in My DP, O(n) solution without using stack:
My solution uses DP. The main idea is as follows: I construct a array longest[], for any longest[i], it stores the longest length of valid parentheses which is end at i.
And the DP idea is :
If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.
Else if s[i] is ')'
If s[i-1] is '(', longest[i] = longest[i-2] + 2
Else if s[i-1] is ')' and s[i-longest[i-1]-1] == '(', longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]
For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.
int longestValidParentheses(string s) {
if(s.length() <= 1) return 0;
int curMax = 0;
vector<int> longest(s.size(),0);
for(int i=1; i < s.length(); i++){
if(s[i] == ')'){
if(s[i-1] == '('){
longest[i] = (i-2) >= 0 ? (longest[i-2] + 2) : 2;
curMax = max(longest[i],curMax);
}
else{ // if s[i-1] == ')', combine the previous length.
if(i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){
longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);
curMax = max(longest[i],curMax);
}
}
}
//else if s[i] == '(', skip it, because longest[i] must be 0
}
return curMax;
}
Updated: thanks to Philip0116, I have a more concise solution(though this is not as readable as the above one, but concise):
int longestValidParentheses(string s) {
if(s.length() <= 1) return 0;
int curMax = 0;
vector<int> longest(s.size(),0);
for(int i=1; i < s.length(); i++){
if(s[i] == ')' && i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){
longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);
curMax = max(longest[i],curMax);
}
}
return curMax;
}
后面这个改写版本是比较无聊的花拳绣腿, 还是看OP自己本来的第一个版本;
这里反正看到了, 我又重新思考了一下这个DP算法; 现在不少解法看下来, 格外发现这里这个DP解法反而是相对比较难想的. DP的一个很难的东西就是找到合适的root involvement用来合理的root decision. 这里这个题目, 相反, entry(返回值)的定义本身倒是不难, 只要是ending at root, 这种involvement我们其实以前是见过好几次的, 这一次就没有想到;
我感觉我做这题的时候一个特别大的毛病还是因为在自己脑子里面build up的太多了, 导致实际上总是暗示自己这个题目最后的算法一定很复杂你肯定想不到, 所以自己最熟悉的ending at root的这种involvement都没有去尝试. 这种毛病真的不要有. 何况这种involvement其实我以前做easy的时候还是自己想出来过好几次的. 给你一个题目, 不要先自己吓自己, 一定要记住: wrong solution is better than no solution. 就算这个题目真的是你铁定做不出来的, 你也尽可能写一个你感觉你能写出来的最好的版本; 上次contest的时候的那个hard, 刚开始也是感觉自己肯定做不出来, 结果最后哪知道随便写的版本就是AC的版本;
@tju_xu97 said in My DP, O(n) solution without using stack:
Thanks for your share. The following is edited from your solution. Just add a prefix.
int longestValidParentheses(string s) {
s = ")" + s;
int curMax = 0;
vector<int> longest(s.size(),0);
for(int i=1; i < s.length(); i++){
if(s[i] == ')' && s[i-longest[i-1]-1] == '('){
longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2];
curMax = max(longest[i],curMax);
}
}
return curMax;
}
python version:
def longestValidParentheses(self, s):
dp, s = [0], ')'+s
for i in xrange(1, len(s), 1):
if s[i] == ')' and s[i - dp[-1] - 1] == '(':
dp.append(dp[-1] + 2 + dp[-2-dp[-1]])
else:
dp.append(0)
return max(dp)
大概看了一下, 他这个就是很巧妙的把一个branch合并到另外一个branch里面了, 也就是s[i-1] == '('的时候, 其实可以跟s[i-1] == ')'合并起来处理; 这个大概自己算一下就可以验证, 不过能想到还是有点想法的;
@jmnjmnjmn said in Simple JAVA solution, O(n) time, one stack:
public class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<Integer>();
int max=0;
int left = -1;
for(int j=0;j<s.length();j++){
if(s.charAt(j)=='(') stack.push(j);
else {
if (stack.isEmpty()) left=j;
else{
stack.pop();
if(stack.isEmpty()) max=Math.max(max,j-left);
else max=Math.max(max,j-stack.peek());
}
}
}
return max;
}
}
这个也是一个类似的做法, 注意看他这里, 他不push右括号, 他只push左括号; 然后用left来记录the index of the last unmatched right parens. 这个算法如果理解了的话, 其实逻辑比editorial那个写法还要直观一些;
@diveintotomorrow said in Simple JAVA solution, O(n) time, one stack:
truly brilliant to store the index into stack (instead of the parentheses)
这个也是我感叹的一个地方; 说起来很trivial, 但是做题的时候就真的未必想得到;
这个是一个相当6的改写:
@EdickCoding said in Simple JAVA solution, O(n) time, one stack:
Nice solution! Inspired by your solution. I changed a little to make it shorter and easier.
public class Solution {
public int longestValidParentheses(String s) {
LinkedList<Integer> stack = new LinkedList<>();
int result = 0;
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
stack.pop();
result = Math.max(result, i - stack.peek());
} else {
stack.push(i);
}
}
return result;
}
}
The idea is simple, we only update the result (max) when we find a "pair".
If we find a pair. We throw this pair away and see how big the gap is between current and previous invalid.
EX: "( )( )"
stack: -1, 0,
when we get to index 1 ")", the peek is "(" so we pop it out and see what's before "(".
In this example it's -1. So the gap is "current_index" - (-1) = 2.
The idea only update the result (max) when we find a "pair" and push -1 to stack first covered all edge cases.
sentinel在handle Corner Case的问题上面, 作用不可小觑. 具体思路本身还是一样的, 关键还是要维护the last unmatched ).
看到这个评论:
@gogoflg2016 said in Simple JAVA solution, O(n) time, one stack:
when I use the Stack instead of LinkedList, I got TLE, can anyone help me figure out why LinkedList used as a stack is faster than Stack presentation.
然后自己实验了一下, 发现了一个很奇怪的东西:
java> Queue<Integer> ls1 = new LinkedList<> ()
java.util.Queue<java.lang.Integer> ls1 = []
java> ls1.push (1)
ERROR: cannot find symbol
symbol: method push(int)
location: variable ls1 of type java.util.Queue<java.lang.Integer>
ls1.push (1);
^
java> ls1.offer (1)
java.lang.Boolean res6 = true
java> ls1.offer (2)
java.lang.Boolean res7 = true
java> ls1
java.util.Queue<java.lang.Integer> ls1 = [1, 2]
java> ls1.peek ()
java.lang.Integer res8 = 1
java> LinkedList<Integer> ls2 = new LinkedList<> ()
java.util.LinkedList<java.lang.Integer> ls2 = []
java> ls2.push (1)
java> ls2.push (2)
java> ls2
java.util.LinkedList<java.lang.Integer> ls2 = [2, 1]
java> ls2.peek ()
java.lang.Integer res10 = 2
java> ls1.poll ()
java.lang.Integer res11 = 1
java> ls2.pop ()
java.lang.Integer res12 = 2
可以看到, LinkedList默认的API居然是Stack, 各种Stack操作都可以使用; 只有你本身用他来初始化一个Queue的变量, 你才能当成一个queue来使用;
java> ls2
java.util.LinkedList<java.lang.Integer> ls2 = []
java> ls2.push (1)
java> ls2.push (2)
java> ls2
java.util.LinkedList<java.lang.Integer> ls2 = [2, 1]
java> ls2.peek ()
java.lang.Integer res19 = 2
java> ls2.pop ()
java.lang.Integer res20 = 2
java> ls2.pop ()
java.lang.Integer res21 = 1
java> ls2
java.util.LinkedList<java.lang.Integer> ls2 = []
java> ls2.offer (1)
java.lang.Boolean res22 = true
java> ls2.offer (2)
java.lang.Boolean res23 = true
java> ls2
java.util.LinkedList<java.lang.Integer> ls2 = [1, 2]
java> ls2.peek ()
java.lang.Integer res24 = 1
java> ls2.poll ()
java.lang.Integer res25 = 1
java> ls2
java.util.LinkedList<java.lang.Integer> ls2 = [2]
java> ls2.pop ()
java.lang.Integer res26 = 2
这个就更奇怪了, 你看peek这个函数, 一会儿是FIFO, 一回是FILO的element; 查了一下文档:
offer: Adds the specified element as the tail (last element) of this list.peek: Retrieves, but does not remove, the head (first element) of this list.poll: Retrieves and removes the head (first element) of this list.push: Pushes an element onto the stack represented by this list.pop: Pops an element from the stack represented by this list.
可以看到, offer这类的操作, 实际上就是LinkedList本身的操作, 针对的就是固定的list的位置进行的最直接的操作; 而pop和push则是很可能就是利用offer类本质操作实现的一个接口操作而已; 所以无论你是当做一个queue用还是当做一个Stack使用, 最后本质都是一个LinkedList; 也不知道怎么讲, 不过看了上面的文档定义, 应该是不难理解之前看到的例子的;
这里这个作者, 就是用LinkedList来实现Stack, 这样比普通的Stack类要快一些;
另外, 居然还有这个黑科技:
@eaglesky said in Simple JAVA solution, O(n) time, one stack:
@gogoflg2016 @quincyhehe Try using ArrayDeque instead of Stack and specify the initial capacity like this:
Dequestack = new ArrayDeque<>(s.length()); Stack and ArrayDeque are implemented with resizable array, and every time it is full, all of the elements will be copied to a new allocated array, which is costly if this process is invoked repeatedly and thus leads to TLE on large test cases. Specifying an initial capacity can prevent this from happening.
头一回听说, 真的是学习了, 也是各种见招拆招的小套路; 还是不能对这些library太有信心;
@pwh1 said in My simple 8ms C++ code:
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
stk.push(-1);
int maxL=0;
for(int i=0;i<s.size();i++)
{
int t=stk.top();
if(t!=-1&&s[i]==')'&&s[t]=='(')
{
stk.pop();
maxL=max(maxL,i-stk.top());
}
else
stk.push(i);
}
return maxL;
}
};
跟上面见到过的一个思路是类似的, -1 sentinel, 和pop&update only when pair.
submission不高兴看了, 基本解法都看过了;
Problem Description
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.
Difficulty:Hard
Total Accepted:116.6K
Total Submissions:502.4K
Contributor:LeetCode
Related Topics
stringdynamic programming
Similar Questions
Valid Parentheses