#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <stack>using namespace std;/*問題: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.分析:此題相當(dāng)于在字符串中尋找最長的有效括號對。如果暴力破解：就枚舉任意開始位置，從該起始位置不斷尋找符合有效括號對的字符，時(shí)間復(fù)雜度應(yīng)該為O(n^2)更特殊的，可以每次找到"("的位置，從該位置進(jìn)行計(jì)算。也可以從后向前尋找"("，記錄dp[i]表示以A[i]為"("的有效長度，下次找到A[i]前面的一個(gè)"("記為A[j],dp[j]={dp[i] + i - j , if A[j]到A[i-1]不是有效括號對 { 0 ,if A[j]到A[i-1]不是有效括號對初始化：對任意,dp[i]=0一旦發(fā)現(xiàn)dp[j]=0,返回dp[i]輸入:(())()())()(())輸出:246報(bào)錯(cuò):Input:"()(())"Output:2Expected:6錯(cuò)在了并沒有考慮(())這種嵌套情況，需要：羅列每個(gè)起始字符關(guān)鍵:1 //string.find(string s , int pos ,int n):pos表示從后向前查找的首個(gè)字符的位置,n表示查找字符串s的前面n個(gè)字符作為查找int index = s.rfind("(" , len);//rfind用于子串查找,find_last_of用于字符匹配2 另外一種解法是:凡是沒有遇到：棧頂為"("，且當(dāng)前字符為")"的情況，就壓入當(dāng)前字符到棧中； 否則，表示找到了一種匹配，則彈出棧頂元素，則此時(shí)棧頂對應(yīng)的是不匹配的元素下標(biāo)，那么匹配的長度 就是當(dāng)前字符的下標(biāo)-棧頂下標(biāo)。 注意之所以初始時(shí)壓入:-1，是為了"()"這種情況的時(shí)候，確保棧頂一定會(huì)存在一個(gè)元素*/class Solution {public: int longestValidParentheses(string s) {if(s.empty()){return 0;}int len = s.length();stack<int> stackInt;stackInt.push(-1);//防止計(jì)算有效長度時(shí)棧為空異常int maxLen = 0;for(int i = 0 ; i < len ;i++){int index = stackInt.top();if(index != -1 && s[i] == ')' && s[index] == '('){stackInt.pop();maxLen = max(maxLen , i - stackInt.top());//這里有效長度=當(dāng)前下標(biāo)-棧頂對應(yīng)下標(biāo)(最后一個(gè)不匹配的下標(biāo))}else{stackInt.push(i);}}return maxLen;}};void PRocess(){string str;while(cin >> str){Solution solution;int result = solution.longestValidParentheses(str);cout << result << endl;}}int main(int argc , char* argv[]){//test();process();getchar();return 0;}
