Longest Valid Parentheses
Total Accepted:4153Total
Submissions:22587My Submissions
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.
每次操作栈和其他容器的时候都要注意是否为空。
这道题的计算要注意,如何才能得到当前最长valid parentheses。
int longestValidParentheses(string s)
{
stack<int> stk;
int len = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '(') stk.push(i);
else
{
if (stk.empty()) stk.push(i);
else
{
if (s[stk.top()] == '(')
{
stk.pop();
if (stk.empty()) len = max(len, i+1);
else len = max(len, i-stk.top());
}
else stk.push(i);
}
}
}
return len;
}
巧妙地利用栈,保留下标,然后根据条件判断,逐步计算出结果。
分支条件有三到四个,也挺容易出错的题目。
-
classSolution{
-
public:
-
intlongestValidParentheses(strings)
-
{
-
intn=s.length();
-
stack<int>stk;
-
intlongestLen=0;
-
for(inti=0;i<n;i++)
-
{
-
if(s[i]=='(')stk.push(i);
-
else
-
{
-
if(stk.empty())
-
{
-
stk.push(i);
-
}
-
else
-
{
-
if(s[stk.top()]!='(')
-
stk.push(i);
-
else
-
{
-
stk.pop();
-
-
if(stk.empty())longestLen=max(longestLen,i+1);
-
elselongestLen=max(longestLen,i-stk.top());
-
}
-
}
-
}
-
}
-
returnlongestLen;
-
}
-
};
分享到:
相关推荐
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
java lru leetcode ...Parentheses](./leetcode/动态规划-Longest Valid Parentheses.java) [动态规划-Maximum Length of Repeated Subarray](./leetcode/动态规划-Maximum Length of Repeated Subar
第四章 Leetcode 题解 ...20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli
leetcode怎么改密码 Code leetcode easy 测试一下本地的... emmmmm之前修改了一下,现在用ssh提交 应该不用输入密码了吧 ~~emmmmm 先在这里立个flag!!...Longest Valid Parentheses :cross_mark:暴力解法(未通过)
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
Leetcode 32 Longest Valid Parentheses (最长有效括号) 给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。 示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2...
Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3
java lru leetcode :ice_cream: LeetCode ...Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** ...Valid Parentheses 022 Generate Parentheses 028 Implement strStr() 031 Next Permutat
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...
Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to ...
leetcode题库 LeetCode 题解合集 本仓库展示了LeetCode题库中部分题目的解法(持续更新),所有代码均采用C++编写并配有输入输出样例 代码清单如下: 序号 题目 程序源码 ...Parentheses.cpp 22 括号生成 G
Parentheses 26.Remove Duplicates from Sorted Array 53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell Stock II 123.Best Time to Buy and Sell Stock...
lru cache leetcode #算法解题报告 主要记录我每天做的题目,包括leetcode, 剑指offer等在线编程平台,以前做过的等时间够再一起分享。 使用swift解题 30-Day ...Parentheses 21.Merge Two Sorted L
LeetCode去除数组重复元素 说明 在leetcode上的题目 ...Parentheses(有效的括号) 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足:左括号必须用相同类型的
Longest Common Prefix 运行时间:40 毫秒内存使用:13.9 MB 20. Valid Parentheses 运行时间:40 毫秒内存使用:13.8 MB 22. Generate Parentheses 运行时间:164 毫秒内存使用:22.5 MB 26. Remove Duplicates ...
Longest Valid Parentheses Largest Rectangle in Histogram Evaluate Reverse Polish Notation Implement Stack using Queues 队列 Implement Queue using Stacks 二叉树 二叉树的遍历 Binary Tree Preorder ...
Longest Common Prefix:这道题和大家思路一样,都是取第一个字符串里的字节与后面的进行比较,只是要注意,针对空vector的返回,针对vector只有一个值时候的返回,和一些通过设置更好初始值进行优化。 20. Valid ...
加油站 leetcode 力码锈 问题 # 标题 命令 1 cargo run ...3-longest-substring-without-repeating-...20-valid-parentheses 21 cargo run --bin 21-merge-two-sorted-lists 27 cargo run --bin 27-remove-element 28