32. 最長有效括號

給你一個只包含 ‘(’ 和 ‘)’ 的字符串，找出最長有效（格式正確且連續）括號子串的長度。

https://leetcode.cn/problems/longest-valid-parentheses/

2.方法二：棧

class Solution {
public:int longestValidParentheses(string s) {int max_len = 0, cur_len = 0;stack<pair<char,int>> sub_s;sub_s.push({' ',-1 });for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {sub_s.push({'(',i});}else {// 如果是）的話if (sub_s.top().first == -1) {// 不可能出現匹配了，記錄失配點sub_s.push({ ')',i });}else {// 棧里有個(if (sub_s.top().first == '(') {sub_s.pop();cur_len = i - sub_s.top().second;if (max_len < cur_len) {max_len = cur_len;}}else {// 否則失配sub_s.push({ ')',i });}}}}return max_len;}
};

1.方法一：動態規劃

class Solution {
public:int longestValidParentheses(string s) {if (s.size() <= 1) {return 0;}vector<int> dp(s.size());dp[0] = 0;int max_len = 0;for (int i = 1; i < s.size(); i++) {if (s[i] == ')' && s[i - 1] == '(') {// 是()()()這樣連著的，就可以逐個累積if (i > 2) {dp[i] = 2 + dp[i - 2];} else {dp[i] = 2;}} else if (s[i] == ')' && s[i - 1] == ')') {// ……)) 這樣的樣子，可能是// 情況1：()) 不匹配// 情況2：(()) 匹配了并且前面沒有可以匹配的了// 情況3：()()()(())匹配而且前面還有可以匹配的if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {if (i - dp[i - 1] - 2 >= 0) {dp[i] = dp[i - dp[i - 1] - 2] + 2 + dp[i - 1];} else {dp[i] = dp[i - 1] + 2;}} else {dp[i] = 0;}} else {dp[i] = 0;}if (max_len < dp[i]) {max_len = dp[i];}}return max_len;}
};

方法三：貪心算法

我覺得這個方法有點類似這個題的算法：

【算法day19】括號生成——數字 n 代表生成括號的對數，請你設計一個函數，用于能夠生成所有可能的并且 有效的 括號組合

也就是說，通過判斷左右括號的數量來判斷是否匹配

但是這個算法沒有考慮()(((()的情況，這個顯然左括號很多，但是右括號嚴重缺少。
所以我們從右往左再類似地看一次，這次判斷 ，左括號數大于右括號數，就失配，令當前匹配數量為0.

class Solution {
public:int longestValidParentheses(string s) {int cur_len = 0, max_len = 0;int left_num = 0, right_num = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {++left_num;} else if (s[i] == ')') {++right_num;}if (right_num > left_num) {right_num = 0;left_num = 0;} else if(right_num==left_num){cur_len = 2 * min(left_num, right_num);if (cur_len > max_len) {max_len = cur_len;}}}left_num = 0, right_num = 0;for (int i = s.size() - 1; i < s.size(); i--) {if (s[i] == '(') {++left_num;} else if (s[i] == ')') {++right_num;}if (right_num < left_num) {right_num = 0;left_num = 0;} else if (right_num == left_num) {cur_len = 2 * min(left_num, right_num);if (cur_len > max_len) {max_len = cur_len;}}}return max_len;}
};