主要介紹棧的一個應(yīng)用，之前做過類似的題目，這次徹底搞懂，記錄之。。
找到最長匹配括號長度，這題比較難，之前刷題的時候就覺得，這次學(xué)到了。 比如說()()()(((最長匹配括號長度為6，((())最長匹配括號長度是4。
1.如果是左括號肯定是壓棧（壓入該左括號在串中的索引）。 2.如果是右括號： 那么就要分兩種情況： 第一種情況是棧不為空，說明找到了匹配的左括號，那么記錄當(dāng)前匹配左括號的長度，并且并且彈棧，彈棧以后又分為兩種情況： （1）棧為空，說明本次匹配完成，用當(dāng)前索引減去start索引 （2）棧不為空，則當(dāng)前匹配長度=當(dāng)前索引-棧頂元素索引 第二種情況是棧為空，說明之前已經(jīng)匹配完了，那么設(shè)置當(dāng)前右括號的位置為新的匹配起點開始記錄。
class Solution {public: int longestValidParentheses(string s) { stack<int> ss; int start = -1; int size=s.size(); int m=0; for(int i=0;i<size;++i) { if(s[i]=='(')//left push { ss.push(i); } else { if(ss.empty()) { start=i; } else { ss.pop(); if(ss.empty()) { m=max(i-start,m); } else { m=max(m,i-ss.top()); } } } } return m; }};新聞熱點
疑難解答
