LeetCode32.Longest Valid Parentheses(Hard)

最長有效括號子字串長度

輸入一個只由 ‘(‘ 或是 ‘)’ 組成的字串，而我們要做的，就是判斷最長的『合理』子字串長度。

比方說， “()” 就是合理的子字串、”)(” 就是個不合理的子字串。

ans1.

從左到右讀一遍、然後再從右讀到左，最後決定最長的長度。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

class Solution { public: int longestValidParentheses(string s) { // Init int max_len = 0; int left = 0; int right = 0; // Left to right for (int i=0; i<s.size(); ++i) { if (s[i] == '(') { ++left; } else { ++right; } if (left == right) { max_len = max(max_len, left+right); } else if (left < right) { left = 0; right = 0; } } // Init left = 0; right = 0; // Right to left for (int i=s.size()-1; i>=0; --i) { if (s[i] == ')') { ++right; } else { ++left; } if (left == right) { max_len = max(max_len, left+right); } else if (left > right) { left = 0; right = 0; } } return max_len; } };

ans2.

創建一個堆疊(stack)，並將-1放入堆疊(stack)作為起始索引(index)

遍歷字串

如果遇到(，將其索引push進堆疊

如果遇到)，從堆疊中pop一個元素，表示配對的(的索引(index)，計算當前有效括號子字串的長度

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: int longestValidParentheses(string s) { stack<int> st; st.push(-1); int ans = 0; for (int i = 0; i < s.size(); ++i) { if (s[i] == ')' && st.top() != -1 && s[st.top()] == '(') { st.pop(); ans = max(ans, i - st.top()); } else st.push(i); } return ans; } };

Ref:

https://www.catxcoder.com/medium/2023/05/26/32-Longest-Valid-Parentheses.html

https://github.com/azl397985856/leetcode/blob/master/problems/32.longest-valid-parentheses.md

https://clay-atlas.com/blog/2021/02/04/leetcode-cn-32-longest-valid-parentheses-solution/