面试金典--面试题 17.21. 直方图的水量（不困难的困难题）

本文主要是介绍面试金典--面试题 17.21. 直方图的水量（不困难的困难题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [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

思路分析

观察图片可知，总面积=黑色面积+蓝色面积。

黑色面积很好求，直接sum(所给数组)就行了。
蓝色面积是答案。所以问题转化成求图中的总面积。

这个其实也很好处理，我们一层一层的去求就好了。

按照所给示例：height=[0,1,0,2,1,0,1,3,2,1,2,1]
第一层：
left=0，right=11，high=1 （high代表当前层数）。当左右指针指向的区域高度小于high时，左右指针都向中间移动，直到指针指向区域大于等于high的值。若不小于high，则指针不移动。
left不断向右靠近，在第一层left=1时，left和right在输入数组height中的数值都大于当前遍历的层数high。所以第一层的体积就是right-left+1

第二层：
第二层，high = 2，left一直向右移动到left = 3，right向左移动到right = 10。所以第二层体积：right - left + 1 = 8。

第三层同理为1。

所以最后的答案就是，刚求得的总体积-所给数组的和。

完整代码

class Solution:def trap(self, height: List[int]) -> int:if not height:return 0zhuzi = sum(height)length = 1 # 表示第几层res = 0while length<=max(height):left = 0right = len(height)-1while height[left]<length:left+=1while height[right]<length:right-=1res += right-left+1length+=1return res-zhuzi

这篇关于面试金典--面试题 17.21. 直方图的水量（不困难的困难题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---