leetcode42:接雨水

给定 n 个非负整数表现每个宽度为 1 的柱子的高度图，盘算按此分列的柱子，下雨之后能接多少雨水。

示例 1：

2. <strong>输入：</strong>height = [0,1,0,2,1,0,1,3,2,1,2,1]
3. <strong>输出：</strong>6
4. <strong>解释：</strong>上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

复制代码

示例 2：

2. <strong>输入：</strong>height = [4,2,0,3,2,5]
3. <strong>输出：</strong>9

复制代码

提示：

• n == height.length
  
• 1 <= n <= 2 * 104
  
• 0 <= height <= 105
  

步调1：界说标题标题性子

盘算标题性子

给定一组表现柱子高度的数组 height，每个元素代表柱子的位置和高度。我们的目标是盘算雨水在这些柱子之间可以或许储存的总量。这是范例的“接雨水”标题。
输入输出条件

• 输入：一个非负整数数组 height，长度为 n，每个元素代表宽度为 1 的柱子高度。
  
• 输出：一个整数，表现可以存储的雨水总量。
  

限定条件

• n == height.length，数组的长度为 n。
  
• 1 <= n <= 2 * 10^4，柱子的数量最多为 20000。
  
• 0 <= height <= 10^5，每个柱子的高度最大为 100000。
  

边界条件

• 如果 n == 1，显然无法存储任何雨水，结果为 0。
  
• 如果全部柱子的高度都为 0，同样也不能存储雨水。
  
• 只有两个柱子的情况下，也不会存储雨水。
  

步调2：解题思绪分解

这类标题可以从以下几种方法动手：
1. 暴力解法

对每个柱子来说，盘算它左右两侧的最大高度，然后根据该柱子的高度，盘算其上方可以存储的雨水量。这个解法时间复杂度为 O(n^2)，不敷高效，尤其在输入规模较大时。
2. 动态规划

为了制止暴力解法的重复盘算，可以提前盘算出每个柱子左右两侧的最大高度，利用两个数组 left_max 和 right_max 分别记载到每个柱子为止，左侧和右侧的最大高度。如许就可以在 O(n) 时间内盘算每个柱子的存储水量。

• 时间复杂度：O(n)
  
• 空间复杂度：O(n)（由于利用了两个额外数组）
  

3. 双指针法（最佳方案）

双指针法通过维护两个指针，一个从左向右，一个从右向左，渐渐盘算每个位置的存水量。通过比力左右两侧的最大高度，更新指针和存水量。这种方法可以在 O(n) 时间内完成盘算，且只须要常数级的额外空间。

• 时间复杂度：O(n)
  
• 空间复杂度：O(1)（只利用了几个额外的变量）
  

办理方案总结

最优方法是双指针法，由于它在时间和空间上都到达了最优。
步调3：C++代码实现

代码剖析：

• 利用 left 和 right 两个指针从数组两端向中心移动。
  
• left_max 和 right_max 分别存储左边和右边遇到的最大高度。
  
• 每次根据 height[left] 和 height[right] 的巨细决定移动哪个指针，并盘算对应位置的存水量。
  
• 当 left 和 right 相遇时，竣事盘算。
  

步调4：开导与优化

通过这道题可以得到的开导是：

• 双指针法的利用可以极大地进步算法的服从，尤其是在处理惩罚雷同的对称性标题时，它制止了不须要的盘算。
  
• 空间优化：我们通过双指针法淘汰了空间复杂度，使得算法可以在不额外存储中心结果的情况下高效完成使命。这种思绪对于处理惩罚大规模数据集非常有效。
  

步调5：现实应用场景分析

这种“接雨水”的标题在现实生存中的应用场景许多，特别是在地理信息体系和修建水力学中。比方：

•         都会排水体系计划：在计划都会下水道时，工程师须要思量差别地域的地形（可以雷同于柱子的高度），并通过算法盘算暴雨期间大概产生的积水量，进而计划公道的排水体系。该算法可以资助模拟大规模地域的降雨积水情况，从而优化排水办法的建立。
  
•         灌溉体系的优化：在农业范畴，尤其是对于不平展的地步，盘算地步之间可以储存的水量对于公道分配水资源非常告急。利用雷同算法可以优化灌溉体系计划，提拔农业水资源的利用服从。
  

这种算法可以通过对高程数据举行分析，推测大概的积水量和流向，进而为差别地域计划最佳的排水办理方案。