钱柜娱乐 > 其他 > 详细

LeetCode-32-Longest Valid Parentheses

时间:2019-02-11 18:19:58      阅读:22      评论:0      收藏:0      [点我收藏+]

标签:str   lan   form   栈模拟   ret   amp   pan   计算   urn   

算法描述:

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 "()()"

解题思路:用栈模拟,遇到左括号进栈,右括号出栈,并计算合法括号数量。

    int longestValidParentheses(string s) {
        stack<int> stk;
        int res = 0;
        int i = 0;
        int start = -1;
        while(i < s.size()){
            if(s[i]==(){
                stk.push(i);
            }else{
                if(stk.empty())
                    start = i;
                else{
                    stk.pop();
                    if(stk.empty())
                        res = max(res, i- start);
                    else
                        res = max(res, i-stk.top());
                }
            }
            i++;
        }
        return res;
    }

 

LeetCode-32-Longest Valid Parentheses

标签:str   lan   form   栈模拟   ret   amp   pan   计算   urn   

原文:https://www.cnblogs.com/nobodywang/p/10362635.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 ♞钱柜娱乐_钱柜娱乐777_钱柜娱乐唯一授权官网-欢迎您
打开钱柜娱乐技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号