算法 经验分享 c++ 栈 Leetcode—32. 最长有效括号【困难】（动态规划及ranges::max()使用）

2024每日刷题（110）

Leetcode—32. 最长有效括号

栈实现代码

class Solution {

public:

int longestValidParentheses(string s) {

stack st;

st.push(-1);

int n = s.size();

int maxn = 0;

for(int i = 0; i < n; i++) {

if(s[i] == '(') {

st.push(i);

} else {

st.pop();

if(st.empty()) {

st.push(i);

} else {

maxn = max(maxn, i - st.top());

}

}

}

return maxn;

}

};

运行结果

动态规划算法思想

实现代码

class Solution {

public:

int longestValidParentheses(string s) {

string s2 = ")" + s;

int n = s2.size();

vector dp(n);

for(int i = 1; i < n; i++) {

if(s2[i] == ')' && s2[i - dp[i - 1] - 1] == '(') {

dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;

}

}

return ranges::max(dp);

}

};

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！

好文推荐