题目描述:
给出 $n$ 个非负整数表示每个宽度为 $1$ 的柱子的高度图,计算按照此排列的柱子,能够接多少雨水。
数据范围:
$1\le n \le 2\times 10^4$
题解:
单调栈:
使用单调栈,维护一个单调减的栈,如果遇到更高的柱子则出栈求贡献,栈内需要存下标,一般存下标比较通用性比较好。出栈求贡献之后需要更新当前液面的高度,以方便下次求贡献。当出栈完毕时需要检查栈是否为空,不为空时需要加上新的贡献。
动态规划:
对于每一个高度 $height[i]$ 需要找出左右两侧的最大高度,然后就可以得到该列的贡献。每次遍历的话复杂度是 $O(n^2)$ ,可以使用动态规划维护这个高度,有点类似悬线法。
双指针
由于动态规划数组实际只用到了一个元素,考虑使用双指针优化。使用两个变量 $leftMax, rightMax$ 替换数组,同时使用双指针 $left,right$ 滑动更新 。
- $leftMax\lt rightMax$ 说明当前位置的贡献为 $leftMax-height[l]$
- $leftMax >= rightMax$ 当前位置的贡献为 $rightMax - height[r]$
因为只要左右两侧有更高的,就会存在贡献。而 $leftMax \ge height[l|r], rightMax \ge height[l|r]$ ,因此左右两侧不存在更高的柱子的情况也不受到影响。
代码:
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
| class Solution { public: const static int maxn = 1e5 + 10; const static int maxm = 1e5 + 10; const static int INF = 0x3f3f3f3f; static void optimize_cpp_stdio() { ios::sync_with_stdio(false), cin.tie(0); } stack<int> st; int trap(vector<int> &height) { optimize_cpp_stdio(); int n = height.size(); int ans = 0; for (int i = 0; i < n; ++i) { int pre = 0; while (st.size() && height[st.top()] <= height[i]) {
ans += (height[st.top()] - pre) * (i - st.top() - 1); pre = height[st.top()]; st.pop(); } if (st.size()) ans += (height[i] - pre) * (i - st.top() - 1); st.push(i); }
return ans; } };
|
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
| class Solution { public: const static int maxn = 1e5 + 10; const static int maxm = 1e5 + 10; const static int INF = 0x3f3f3f3f; static void optimize_cpp_stdio() { ios::sync_with_stdio(false), cin.tie(0); } int trap(vector<int> &height) { optimize_cpp_stdio(); int n = height.size(); int l, r, lm, rm; l = 0, r = n - 1; lm = rm = 0; int ans = 0; while (l < r) { lm = max(height[l], lm); rm = max(height[r], rm); if (lm < rm) ans += lm - height[l++]; else ans += rm - height[r--]; } return ans; } };
|