032最長有效括號
題目描述:
給定一個只包含'('
和 ')'
的字串,找出最長的包含有效括號的子串的長度。
示例 1:
"()"
示例 2:
輸入: ")()())
" 輸出: 4 解釋: 最長有效括號子串為"()()"
解題思路:
這裡我們還是藉助棧來求解,需要定義個start變數來記錄合法括號串的起始位置,我們遍歷字串,如果遇到左括號,則將當前下標壓入棧,如果遇到右括號,如果當前棧為空,則將下一個座標位置記錄到start,如果棧不為空,則將棧頂元素取出,此時若棧為空,則更新結果和i - start + 1中的較大值,否則更新結果和i - 棧頂元素中的較大值。
1 class Solution { 2 public: 3int longestValidParentheses(string s) { 4if (s.size() < 2)return 0;//字元太短,無法組成括號 5int start = 0, res = 0; 6stack<int>num; 7for (int i = 0; i < s.size(); ++i) { 8if (s[i] == '(')num.push(i); 9else { 10if (num.empty())start = i + 1; 11else { 12num.pop(); 13if (num.empty())res = res > i - start + 1 ? res : i - start + 1; 14else res = res > i - num.top() ? res : i - num.top(); 15} 16} 17} 18return res; 19} 20 };