空间换时间专题 2020-10-28 | | Algorithm | Algorithm 42. 接雨水此题首先需知如何计算总雨水量: 总雨水量的计算需知数组中的每个数左侧和右侧的最高值,取二者较小值减去当前高度,即为当前点处能蓄水的量 如果不用空间换时间,计算每个点左右两侧的最大值都需要遍历一次所有数据 所以用两个数组leftMax和rightMax分别存储每个点左侧的最大值和右侧的最大值 最后再一次遍历计算总蓄水量