企业官网建设流程全解析

这个题目属于面试，秋招校招最高频手撕代码题目之一了，必须熟练。

一、题目

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

示例 1：

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

示例 2：

输入：height = [4,2,0,3,2,5]输出：9

二、解答实现

2.1 前缀最大值

想象当前位置能够接到的雨水，它取决于当前位置左边的最大高度以及右边的最大高度，这二者中取最小值，然后再减去当前位置的高度。相当于左边要选出高的把水接住，右边也必须选出高的接住水，要不然水会漏出去。但是这二者之间还必须取最小的才能是当前位置的水量。求取左右前缀最大值就是从前向后遍历一次，然后倒着向前遍历一次即可。

from typing import List class Solution: def trap(self, height: List[int]) -> int: ans = 0 n = len(height) pre_max = [0] * n suf_max = [0] * n pre_max[0] = height[0] for i in range(0, n): pre_max[i] = max(pre_max[i - 1], height[i]) suf_max[-1] = height[-1] for j in range(n - 2, -1, -1): suf_max[j] = max(suf_max[j + 1], height[j]) for h, pre, suf in zip(height, pre_max, suf_max): ans += min(pre, suf) - h return ans

2.2 双指针

上面2.1节中介绍的方法其时间复杂度是O(n)的，由于使用了两个数组，空间复杂度也是O(n)的。这个时候我们如果想要节省空间复杂度，就需要引入双指针，通过动态的变量替换掉数组。

from typing import List class Solution: def trap(self, height: List[int]) -> int: ans = 0 left = 0 # 左边指针，记录pre_max right = len(height) - 1 # 右边指针，记录suf_max pre_max = 0 suf_max = 0 while left <= right: pre_max = max(pre_max, height[left]) suf_max = max(suf_max, height[right]) # 如果左边最大值小于右边最大值，那么当前水的容量就可以知道了 if pre_max < suf_max: ans += pre_max - height[left] left += 1 else: ans += suf_max - height[right] right -= 1 return ans