本文主要是介绍32. Longest Valid Parentheses(Leetcode每日一题-2020.07.04),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Problem
Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
来源:力扣(LeetCode)
Example1
Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”
Example2
Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”
Solution
一个合法的括号序列满足下面两条性质
class Solution {
public:int longestValidParentheses(string s) {int ret = 0;int start = -1; //分段起点的前一个位置stack<int> stk;for(int i = 0;i<s.length();++i){if(s[i] == '(')//左括号直接入栈{stk.push(i);} else{if(!stk.empty())//当前是右括号,且栈里还有左括号{stk.pop();//左括号弹栈if(!stk.empty())//如果栈不为空,即还有左括号{ret = max(ret,i - stk.top());}else如果栈不为空,即没有左括号,说明当前的右括号可以匹配这一段最左侧的左括号{ret = max(ret,i - start);}}else//当前是右括号,栈里没有左括号,说明该右括号是使得右括号数量大于左括号数量的第一个位置{start = i;}}}return ret;}
};
这篇关于32. Longest Valid Parentheses(Leetcode每日一题-2020.07.04)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!