The trap function takes an input vector height of non-negative integers representing the elevation map. The goal is to calculate the amount of water that can be trapped after raining.
The solution uses a two-pointer approach. We start with two pointers left and right at the leftmost and rightmost positions of the height vector, respectively. We also have two variables leftMax and rightMax to keep track of the maximum height seen so far on the left and right sides, respectively.
The basic idea of the two-pointer approach is to move the pointer pointing to the lower height towards the center, so that we can calculate the trapped water between the two pointers. To implement this idea, we compare the height of the bars at left and right positions, and move the pointer pointing to the lower height towards the center.
If height[left] < height[right], we increment left. If height[left] >= leftMax, we update leftMax with the current height. If height[left] < leftMax, it means that water can be trapped between the current position and the previous maximum height. We add leftMax - height[left] to the result res.
The same logic applies to the case where height[right] <= height[left]. If height[right] >= rightMax, we update rightMax with the current height. If height[right] < rightMax, we add rightMax - height[right] to the result res.
We keep repeating this process until left >= right. At the end, res will contain the total amount of trapped water.
The time complexity of this solution is O(n), because we traverse the height vector once with two pointers. The space complexity is O(1), because we only need a constant amount of extra memory to store leftMax, rightMax, and res.
时间复杂度
time complexity of O(n) and a space complexity of O(1).
参考文献
chatGPT
C++ 代码
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
int left = 0, right = n - 1;
int leftMax = 0, rightMax = 0;
int res = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) leftMax = height[left];
else res += leftMax - height[left];
left++;
} else {
if (height[right] >= rightMax) rightMax = height[right];
else res += rightMax - height[right];
right--;
}
}
return res;
}
};