目录
2024-03-15 leetcode写题记录
32. 最长有效括号
题目链接
题意
给你一个只包含$ '\((\)' 和 '\()\)' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
解法
动态规划
用\(dp[i]\)代表从第\(i\)个字符串开始，最多往前多少个字符是合法的。那么当我们遍历\(s\)时，第\(i\)个字符只需要跟第\(i-dp[i-1]-1\)（这里为了方便，记为\(l\)）处的字符比较。
当\(l<=0\)时，代表没有字符能够跟第\(i\)个字符配对了，显然\(dp[i]=0\)；当第\(i\)个字符为'\((\)'时，由于第\(i\)个字符无法配对（右边没有字符了），所以\(dp[i]=0\)；当第\(l\)个字符为'\()\)'时，由于从第\(l+1\)到第\(i-1\)的字符都已经合法了，而第\(i\)个字符无法与第\(l\)个字符配对，所以也有\(dp[i]=0\)。
只有当第\(l\)个字符为'\((\)'且第\(i\)个字符为'\()\)'时，才能完成状态转移，方程为\(dp[i]=dp[i-1]+2+dp[l-1]\)。
从所有\(dp[i]\)里找到最大的那个，就是答案。
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size(), ans = 0;
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; ++i) {
int l = i - dp[i - 1] - 1;
if (l <= 0 || s[i - 1] == '(' || s[l - 1] == ')')
continue;
dp[i] = dp[i - 1] + 2 + dp[l - 1];
ans = max(ans, dp[i]);
}
return ans;
}
};
42. 接雨水
题目链接
题意
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解法
动态规划
时间复杂度\(O(n)\)，空间复杂度\(O(n)\)。
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
vector<int> l(n + 2, 0), r(n + 2, 0);
for (int i = 1; i <= n; ++i)
l[i] = max(l[i - 1], height[i - 1]);
for (int i = n; i >= 1; --i)
r[i] = max(r[i + 1], height[i - 1]);
int ans = 0;
for (int i = 1; i <= n; ++i) {
int lr = min(l[i - 1], r[i + 1]);
if (lr <= height[i - 1])
continue;
ans += lr - height[i - 1];
}
return ans;
}
};
双指针
用\(l\)和\(r\)遍历，若\(l\)左边的最大值已经小于\(r\)右边的最大值，那么\(l\)左边的最大值一定小于\(l+1\)右边的最大值，所以就可以把第\(l+1\)个元素的贡献加上，然后\(l\)右移\(1\)位，反之同理。
时间复杂度\(O(n)\)，空间复杂度\(O(1)\)。
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size(), l = 0, r = n - 1, ans = 0, ml = 0, mr = 0;
while(l < r) {
ml = max(ml, height[l]);
mr = max(mr, height[r]);
if (ml < mr) {
if (ml > height[l + 1])
ans += ml - height[l + 1];
l++;
} else {
if (mr > height[r - 1])
ans += mr - height[r - 1];
r--;
}
}
return ans;
}
};