直方图的水量 力扣面试题 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

思路:

左右视图,同一位置取较小值, 便是当前位置能够储水的最大高度, 最后在减去构成容器的直方图的高度,就是最终储水的结果

int trap(vector<int>& height) {// 从左向右得到直方图的左视图, 在得到右视图, 每个位置取较小值int res = 0;pty())return res;vector<int> left(height.size(), 0);vector<int> right(height.size(), 0);int lmax, rmax = 0;for(int i = 0; i < height.size(); ++i){// 从左向右, 得到直方图的左视图left[i] = max(lmax, height[i]);if(lmax < height[i])lmax = height[i];// 从右向左,得到直方图的右视图right[height.size()-1-i] = max(rmax, height[height.size()-1-i]);if(rmax < height[height.size()-1-i])rmax = height[height.size()-1-i];}for(int i = 0; i < height.size()-1; ++i){// 取左,右视图同一位置处, 较小值就是就可以储水的最高高度, 再减去构成直方图的值res += (min(left[i], right[i]) - height[i]);}return res;}