Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
Solution 1: Brute Force
r[i] = min(max(h[0:i+1]), max(h[i:n]))
ans = sum(r[i])
Time complexity: O(n^2)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: int trap(vector<int>& height) { const int n = height.size(); int ans = 0; auto sit = cbegin(height); auto eit = cend(height); for (int i = 0; i < n; ++i) { int l = *max_element(sit, sit + i + 1); int r = *max_element(sit + i, eit); ans += min(l, r) - height[i]; } return ans; } }; |
Solution 2: DP
l[i] := max(h[0:i+1])
r[i] := max(h[i:n])
ans = sum(min(l[i], r[i]) – h[i])
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int trap(vector<int>& height) { const int n = height.size(); vector<int> l(n); vector<int> r(n); int ans = 0; for (int i = 0; i < n; ++i) l[i] = i == 0 ? height[i] : max(l[i - 1], height[i]); for (int i = n - 1; i >= 0; --i) r[i] = i == n - 1 ? height[i] : max(r[i + 1], height[i]); for (int i = 0; i < n; ++i) ans += min(l[i], r[i]) - height[i]; return ans; } }; |
Solution 3: Two Pointers
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 4 ms, 9.1 MB class Solution { public: int trap(vector<int>& height) { const int n = height.size(); if (n == 0) return 0; int l = 0; int r = n - 1; int max_l = height[l]; int max_r = height[r]; int ans = 0; while (l < r) { if (max_l < max_r) { ans += max_l - height[l]; max_l = max(max_l, height[++l]); } else { ans += max_r - height[r]; max_r = max(max_r, height[--r]); } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment