直方图的水量
难度:
标签:
题目描述
Imagine a histogram (bar graph). Design an algorithm to compute the volume of water it could hold if someone poured water across the top. You can assume that each histogram bar has width 1.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
代码结果
运行时间: 29 ms, 内存: 16.6 MB
/*
* 思路：
* 1. 使用 Java Stream 来计算 leftMax 和 rightMax 数组。
* 2. 通过流的操作来遍历数组并计算每个位置能存储的水量。
*/
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) return 0;
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = height[0];
IntStream.range(1, n).forEach(i -> leftMax[i] = Math.max(leftMax[i - 1], height[i]));
rightMax[n - 1] = height[n - 1];
IntStream.iterate(n - 2, i -> i >= 0, i -> i - 1).forEach(i -> rightMax[i] = Math.max(rightMax[i + 1], height[i]));
return IntStream.range(0, n).map(i -> Math.min(leftMax[i], rightMax[i]) - height[i]).sum();
}
}解释
方法:
此题解采用双指针法计算直方图中的水量。初始化两个指针，left指向数组的起始位置，right指向数组的结束位置。同时，设置两个变量leftmax和rightmax来记录从左侧和右侧遍历时遇到的最大高度。通过比较两个指针所指向的高度，决定是移动left指针还是right指针。若height[left]小于height[right]，检查当前left指向的高度是否大于leftmax；如果大于，更新leftmax；否则，计算leftmax和当前高度的差值加到结果res中，表示这部分可以积水的量。同理，若height[right]小于或等于height[left]，则检查right指向的高度与rightmax，并作类似处理。这样，直到left与right指针相遇，遍历结束，得到总的积水量。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在双指针法中，当height[left] < height[right]时只移动left指针，而当height[right] <= height[left]时只移动right指针？这种选择有何算法逻辑上的依据？
▷🦆
在实现中，leftmax和rightmax被初始化为-1，这是否意味着该算法假定所有的直方图高度都是非负的？如果数组中存在负值，这种方法是否仍然有效？
▷🦆
题解中提到的累加积水量的计算方法是基于leftmax和rightmax与当前高度的差值。这种计算是否考虑了两边高度不一致的情况，即一边远高于另一边时？
▷