首页
登录 | 注册

[LeetCode] Longest Valid Parentheses 最长有效括号

 

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

 

这道求最长有效括号比之前那道 Valid Parentheses 难度要大一些,这里我们还是借助栈来求解,需要定义个start变量来记录合法括号串的起始位置,我们遍历字符串,如果遇到左括号,则将当前下标压入栈,如果遇到右括号,如果当前栈为空,则将下一个坐标位置记录到start,如果栈不为空,则将栈顶元素取出,此时若栈为空,则更新结果和i - start + 1中的较大值,否则更新结果和i - 栈顶元素中的较大值,代码如下:

 

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0, start = 0;
        stack<int> m;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') m.push(i);
            else if (s[i] == ')') {
                if (m.empty()) start = i + 1;
                else {
                    m.pop();
                    res = m.empty() ? max(res, i - start + 1) : max(res, i - m.top());
                }
            }
        }
        return res;
    }
};

 

还有一种利用动态规划Dynamic Programming的解法,可参见网友喜刷刷的博客

 

类似题目:

Remove Invalid Parentheses

Different Ways to Add Parentheses

Generate Parentheses

Valid Parentheses

 

参考资料:

https://leetcode.com/problems/longest-valid-parentheses/

 

LeetCode All in One 题目讲解汇总(持续更新中...)


相关文章

  • 代码审查作业
    代码审查 我对结对同伴的代码进行了审查,他的有关括号匹配的代码 审查结果 功能模块名称 括号匹配问题 审查人 牛斌帅 审查日期 2019年4月25日 代码名称 括号匹配问题 代码作者 房旭 文件结构 重要性 审查项 结论 头文件和定义文件的 ...
  • 前言:最近一直在刷leetcode的题,用到isalnum函数,用man手册查找了一下,总共有13个相关函数如下: #include <ctype.h> int isalnum(int c); int isalpha(int c ...
  • 前言:取得成功的要自律!可能有一腔热血,努力很长一阵子,但过一阵子之后,就不坚持了,所以要自律去约束自己时刻坚持着! 一.收获 8月份的收获还是很大的,主要有以下几个方面: 学会了使用github 注册账号很长时间了,但不怎么会用,这个月, ...
  • Day2----Python学习之路笔记(2)
    学习路线: Day1 Day2 Day3 Day4 Day5 ...待续 一.简单回顾一下昨天的内容 1. 昨天了解到了一些编码的知识 1.1. 我们写好的.py文件头没有加# -*- coding:utf-8 -*-这样的声明,那么在Wi ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.059 s.
京ICP备10005923号