社区讨论LinuxDo 最新
Leetcode每日一题 —— 32. 最长有效括号
力扣 LeetCode 32. 最长有效括号 - 力扣（LeetCode） 32. 最长有效括号 - 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。 左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。 示例 1： 输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()" 示例 2： 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()" 示例 3： 输入：s = "" 输出：0…
内容摘要
作者：#SomeBottle
板块：#开发调优
力扣 LeetCode
32. 最长有效括号 - 力扣（LeetCode）
32. 最长有效括号 - 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
* 0...
比较经典的 hot100 题。
思路
两趟扫描可以解决，扫描的顺序决定了我们怎么看待一个连续子序列的括号是否是不闭合的。
从左至右扫描时，我们关注的是右括号数量是否大于左括号数量（因为不知道左括号是不是多了，但我肯定能知道右括号是不是多了，比如 "(()))" 这种情况），即不闭合；反过来从右至左扫描时，我们关注左括号数量是否大于右括号数量。二者数量相同时则得到一个合法序列；如果不闭合，那么之后的序列如果包含当前这个序列，也都是不闭合的，所以要抛弃掉不闭合的序列。
代码
class Solution {
public:
int longestValidParentheses(string s) {
// 可以两趟扫描解决
int n=s.size();
int left=0; // 左括号个数
int right=0; // 右括号个数
int res=0;
for(int i=0;i<n;i++){
if(s[i]=='('){
left++;
}else if(s[i]==')'){
资讯来源
LinuxDo