1. 题目
2. 读题(需要重点注意的东西)
思路1(观察法):
按每一列能存多少水来看:
我们观察到每一列能存水的深度是由它左边的最高矩形条和右边的最高的矩形条决定的,若当前为height[i]
,其左侧最高的矩形条为left[i]
,右侧最高的矩形条为right[i]
,则当前列能存水的高度为min(left[i],right[i]) - height[i]
。
注意:第一列和最后一列不会存水
3. 解法
---------------------------------------------------解法1---------------------------------------------------:
class Solution {
public int trap(int[] height) {
int n = height.length;
if(n == 0) return 0;
int[] left = new int[n];
int[] right = new int[n];
left[0] = height[0];
right[n-1] = height[n-1];
// 找每个i左边的最大值
for(int i = 1;i < n;i++) left[i] = Math.max(left[i-1],height[i]);
// 找每个i右边的最大值
for(int i = n - 2;i >= 0;i--) right[i] = Math.max(right[i+1],height[i]);
// 找每一列能存的水量
int res = 0;
for(int i = 0;i < n;i++) res += Math.min(left[i],right[i]) - height[i];
return res;
}
}
可能存在的问题: