直方图的水量（面试题17.21）

题目

算法

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

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

算法

动态规划

我们通过遍历数组，找到每个位置的可以容纳的最小水量，相加即可得到结果

我们可以通过从左向右开始扫描数组，在数组leftMax中保存每个位置左侧的最大值，也就是这个位置在不考虑右侧的情况下可以容纳的最大水量

然后在自右向左进行一次扫描，在数组rightMax中保存每个位置右侧的最大值，也就是这个位置在不考虑左侧的情况下可以容纳的最大水量

然后我们自左向右再遍历数组，每个位置取leftMax和rightMax中的最小值（大的值因为没有考虑一侧的情况不满足），然后减去height中对应的值（不能盛水的部分）就得到了结果

const trap = height => {
	if (height.length <= 2) return 0;

	let leftMax = [height[0]];
	for (let i = 1; i < height.length; i++) {
		leftMax.push(Math.max(leftMax[i - 1], height[i]));
	}

	let rightMax = [height[height.length - 1]];
	for (let i = height.length - 2; i >= 0; i--) {
		rightMax.unshift(Math.max(height[i], rightMax[0]));
	}

	let totalWater = 0;
	for (let i = 0; i < height.length; i++) {
		totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
	}

	return totalWater;
};

双指针

声明双指针left指向最左侧，right指向最右侧，声明变量leftMax来保存当前位置及其左侧的最大值，rightMax保存当前位置及其右侧的最大值

然后我们移动双指针：

• 判断当前位置left的值和保存的左侧最大值leftMax中的最大值，赋值给leftMax；对于rightMax同样如此
• 如果left指向的值小于right指向的值，我们使用leftMax - height[left]计算出当前位置能存储的最大水量，并加入结果，然后右移指针left++
• 如果right指向的值小于等于left指向的值，我们使用rightMax - height[right]计算出当前位置存储的最大水量，并加入结果，然后左移指针right--
• 直到两指针相遇left >= right，否则重新重复判断

第二三步总是移动指向值较小的那个指针，因为我们最终相遇的时候需要两指针指向整个水槽中最大的那个位置

const trap = height => {
	if (height.length <= 2) return 0;
	let totalWater = 0;
	let left = 0,
		right = height.length - 1;
	let leftMax = 0,
		rightMax = 0;
	while (left < right) {
		leftMax = Math.max(leftMax, height[left]);
		rightMax = Math.max(rightMax, height[right]);
		if (height[left] < height[right]) {
			totalWater += leftMax - height[left];
			left++;
		} else {
			totalWater += rightMax - height[right];
			right--;
		}
	}
	return totalWater;
};