首页 > 代码库 > LeetCode "Longest Valid Parentheses"
LeetCode "Longest Valid Parentheses"
Your intuition would tell you that there‘s a O(n) solution. Actually it is another stack-based problem to solve.
class Solution {public: struct Rec { Rec(char _c, int _inx) : c(_c), inx(_inx) {} char c; int inx; }; int longestValidParentheses(string s) { int len = s.length(); if (len <= 1) return false; // Init vector<int> rec; rec.resize(len); std::fill(rec.begin(), rec.end(), 0); // 1st pass - mark stack<Rec> stk; for (int i = 0; i < len; i++) { char c = s[i]; if (c == ‘(‘) { stk.push(Rec(‘(‘, i)); } else { if (stk.empty()) stk.push(Rec(‘)‘, i)); else { Rec &top = stk.top(); if (top.c == ‘)‘) { stk.push(Rec(‘)‘, i)); } else { rec[top.inx] = i - top.inx + 1; for (int i = top.inx + 1; i < top.inx + rec[top.inx]; i++) { rec[i] == 0; } stk.pop(); } } } }// for // 2nd - calc int max = 0; int j = 0; while (j < len) { int curr = 0; if (rec[j] > 0) { while (rec[j] > 0) { curr += rec[j]; j += rec[j]; if (j >= len) break; } max = std::max(max, curr); } else { j ++; } } return max; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。