关于加强教体局网站建设,wordpress 定时显示,网站的建设步骤有哪些,毕设用别人网站做原型给定一个仅包含字符的字符串(’ 和 ‘)’#xff0c;返回最长有效的长度(出色地-形成) 括号子弦。
示例1#xff1a;
输入#xff1a;s “(()” 输出#xff1a;2 说明#xff1a;最长的有效括号子字符串是 “()” 。
示例2#xff1a;
输入#xff1a;s “)()())… 给定一个仅包含字符的字符串(’ 和 ‘)’返回最长有效的长度(出色地-形成) 括号子弦。
示例1
输入s “(()” 输出2 说明最长的有效括号子字符串是 “()” 。
示例2
输入s “)()())” 输出4 说明最长的有效括号子字符串是 “()()” 。
示例3
输入s “” 输出0
约束
0 s.length 3* 104 s[i] 是 ‘(’ 或者 ‘)’。
解决方案
方法 在这里方法无非是我们使用堆栈当我们遇到开头支撑时我们将其索引推入堆栈中每当我们触摸闭合支架时我们就会看到堆栈的顶部如果它的大小是一个则意味着闭合括号已经统治了开头括号。然后我们将堆栈的最高值编辑为闭合支架的索引。 如下所示图片清楚地描绘了此方法。 在这里给出作为行Ans max给出的答案(ans索引- stk.top()) 只有当堆栈的大小不是1时就会遇到闭合支架。
代码
class Solution {
public:int longestValidParentheses(string s) {stackintstk;stk.push(-1);int ans 0;for(int i 0 ; i s.size(); i){if(s[i] ()stk.push(i);else{if(stk.size() 1)stk.top() i;else{stk.pop();ans max(ans , i - stk.top());}}}return ans;}
};class Solution {public int longestValidParentheses(String s) {int leftCount 0;int rightCount 0;int maxLength 0;for (int i 0; i s.length(); i) {if (s.charAt(i) () {leftCount;} else {rightCount;}if (leftCount rightCount) {maxLength Math.max(maxLength, 2 * rightCount);} else if (rightCount leftCount) {leftCount rightCount 0;}}leftCount rightCount 0;for (int i s.length() - 1; i 0; i--) {if (s.charAt(i) () {leftCount;} else {rightCount;}if (leftCount rightCount) {maxLength Math.max(maxLength, 2 * leftCount);} else if (leftCount rightCount) {leftCount rightCount 0;}}return maxLength;}
}class Solution:def longestValidParentheses(self, s: str) - int:stack[]l[0]*len(s)for ind,i in enumerate(s):if i(:stack.append(ind)else:if stack:l[stack.pop()]1l[ind]1return max(len(i) for i in .join(l).split(0))
复杂
时间复杂性这里的复杂性是 o ( n ) o(n) o(n)因为我们仅使用一个只有一个带有堆栈的循环因此它以线性复杂性运行。空间复杂性这里的空间复杂性将为$ o(n)$因为我们只使用了一个堆栈它也将元素也存储在最坏的情况下因此可以使人变得复杂。
