#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.分析:此题相当于在字符串中寻找最长的有效括号对。如果暴力破解：就枚举任意开始位置，从该起始位置不断寻找符合有效括号对的字符，时间复杂度应该为O(n^2)更特殊的，可以每次找到"("的位置，从该位置进行计算。也可以从后向前寻找"("，记录dp[i]表示以A[i]为"("的有效长度，下次找到A[i]前面的一个"("记为A[j],dp[j]={dp[i] + i - j , if A[j]到A[i-1]不是有效括号对 { 0 ,if A[j]到A[i-1]不是有效括号对初始化：对任意,dp[i]=0一旦发现dp[j]=0,返回dp[i]输入:(())()())()(())输出:246报错:Input:"()(())"Output:2Expected:6错在了并没有考虑(())这种嵌套情况，需要：罗列每个起始字符关键:1 //string.find(string s , int pos ,int n):pos表示从后向前查找的首个字符的位置,n表示查找字符串s的前面n个字符作为查找int index = s.rfind("(" , len);//rfind用于子串查找,find_last_of用于字符匹配2 另外一种解法是:凡是没有遇到：栈顶为"("，且当前字符为")"的情况，就压入当前字符到栈中； 否则，表示找到了一种匹配，则弹出栈顶元素，则此时栈顶对应的是不匹配的元素下标，那么匹配的长度 就是当前字符的下标-栈顶下标。 注意之所以初始时压入:-1，是为了"()"这种情况的时候，确保栈顶一定会存在一个元素*/class Solution {public: int longestValidParentheses(string s) {if(s.empty()){return 0;}int len = s.length();stack<int> stackInt;stackInt.push(-1);//防止计算有效长度时栈为空异常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());//这里有效长度=当前下标-栈顶对应下标(最后一个不匹配的下标)}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;}
