[LeetCode]32.Longest Valid Parentheses

题目

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.

思路

栈中保存的不是字符(而是字符(所在的下标。
如果遇到字符(,无条件压入栈中;
如果遇到字符),并且栈为空,说明这是一个无法匹配的字符),用变量last记录下标。last存放的其实是最后一个无法匹配的字符)。
如果遇到字符),并且栈不为空,我们可以消除一对括号(栈顶元素出栈)。

  • 如果栈为空,用当前元素下标i 减去 last计算有效长度;
  • 如果栈不为空,用当前元素下标i 减去 栈顶元素下标计算有效长度;

代码

/*---------------------------------------------------------
*   日期:2015-04-23
*   作者:SJF0115
*   题目: 32.Longest Valid Parentheses
*   网址:https://leetcode.com/problems/longest-valid-parentheses/
*   结果:AC
*   来源:LeetCode
*   博客:
------------------------------------------------------------*/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        int size = s.size();
        if(size <= 1){
            return 0;
        }//if
        int last = -1;
        int Max = 0;
        stack<int> leftStack;
        for(int i = 0;i < size;++i){
            // (入栈
            if(s[i] == '('){
                leftStack.push(i);
            }//if
            else if(s[i] == ')'){
                if(leftStack.empty()){
                    last = i;
                }//if
                else{
                    leftStack.pop();
                    if(leftStack.empty()){
                        Max = max(Max,i - last);
                    }//if
                    else{
                        Max = max(Max,i - leftStack.top());
                    }//else
                }//else
            }//else
        }//for
        return Max;
    }
};

int main(){
    Solution solution;
    string str("()(()");
    cout<<solution.longestValidParentheses(str)<<endl;
    return 0;
}

运行时间

时间: 2024-12-09 01:33:46

[LeetCode]32.Longest Valid Parentheses的相关文章

LeetCode 32 Longest Valid Parentheses(最长有效括号)(*)

翻译 给定一个仅仅包含"("或")"的字符串,找到其中最长有效括号子集的长度. 对于"(()",它的最长有效括号子集是"()",长度为2. 另一个例子")()())",它的最长有效括号子集是"()()",其长度是4. 原文 Given a string containing just the characters '(' and ')', find the length of the l

Longest Valid Parentheses

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 &

[LeetCode] 20.Valid Parentheses

[题目] Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]

leetcode 20 Valid Parentheses 括号匹配

Given a string containing just the characters '(', ')', '{', '}', '[' and']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]"

LeetCode 20 Valid Parentheses(有效的括号)

翻译 给定一个只包含'(', ')', '{', '}', '[' 和']'的字符串,判断这个输入的字符串是否是有效的. 括号必须在正确的形式下闭合,"()" 和"()[]{}" 是有效的,但是 "(]" 和"([)]" 则不是. 原文 Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the

[LeetCode] Valid Parentheses

Given a string containing just the characters '(',')','{','}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" a

leetcode 5 Longest Palindromic Substring--最长回文字符串

问题描述 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的.比如"a" , "aaabbaaa" 之前

[LeetCode]--14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; String prefix = strs[0]; for (int i = 1; i < strs.lengt

[LeetCode]128.Longest Consecutive Sequence

[题目] Longest Consecutive Sequence  Total Accepted: 4743 Total Submissions: 17989My Submissions Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given [100, 4, 200, 1, 3, 2], The longest c