【程序员面试金典】面试题 17.21. 直方图的水量-Toy模板网

这篇具有很好参考价值的文章主要介绍了【程序员面试金典】面试题 17.21. 直方图的水量。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

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

【程序员面试金典】面试题 17.21. 直方图的水量

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

思路：最直观的想法是，当前直方图所能存储水量等于左边最大值和右边最大值之间的最小值减去当前高度，直方图的水量即所有直方图的水量之和。首先分别前向遍历、后向遍历求出当前直方图左边(包含当前)、右边(包含当前)的最大值，然后再前向遍历求出当前直方图水量即可。

int trap(vector<int>& height) 
{
  int n=height.size();
  //特殊判断
  if(n==0)
    return 0;
  //存储当前元素左边(包含当前)的最大值
  vector<int> left(n,0);
  //存储当前元素右边(包含当前)的最大值
  vector<int> right(n,0);
  left[0]=height[0];
  right[n-1]=height[n-1];
  for(int i=1;i<n;i++)
     left[i]=max(left[i-1],height[i]);
  for(int i=n-2;i>=0;i--)
     right[i]=max(right[i+1],height[i]);
  int res=0;
  //所能存储水量等于左边最大值和右边最大值之间的最小值减去当前高度
  for(int i=0;i<n;i++)
     res+=min(left[i],right[i])-height[i];
  return res;
}

总结：注意，之所以包含当前，是为了方便计算，因为有可能当前就是最高的。文章来源地址https://www.toymoban.com/news/detail-512557.html

到了这里，关于【程序员面试金典】面试题 17.21. 直方图的水量的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！