题目描述:
https://leetcode.com/problems/trapping-rain-water/
解决方法:
https://leetcode.com/problems/trapping-rain-water/solution/
optim_code(c++):
int trap(vector<int>& height)
{
int left = 0, right = height.size() - 1;
int ans = 0;
int left_max = 0, right_max = 0;
while (left < right) {
if (height[left] < height[right]) {
height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
++left;
}
else {
height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
--right;
}
}
return ans;
}
心得:
Approach 1: Brute force
将问题分割的思想,并不是一次一个部分trap的大小,而是进行分解,一次就求解一个上面trap的大小。在算左侧最大时,会把本身的值算进去。因为trap必须比本身大。右侧同理。
Approach 2: Dynamic Programming
方法中依次找出左侧或者右侧最大的值的思想很好,每次都是max(height[i], left_max[i - 1]),其实就是找到了左侧的最大值。右侧同理。
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
left_max | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 |
right_max | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 1 |
Approach 3: Using stacks
思路奇特,较难理解
Approach 4: Using 2 pointers
需观察算法特点,在approach2的基础基础上优化
网友评论