面试题 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

Reference

注：本题与42. 接雨水相同。

题解

#define MAX(x, y) ((x) > (y) ? x : y)
#define MIN(x, y) ((x) < (y) ? x : y)
#define ABS(x) ((x) > 0 ? (x) : -(x))
int trap(int* height, int heightSize){
    int highest = 0, higher = 0, highestIndex = -1, higherIndex = -1, i = 0, ret = 0;
    for (i = 0; i < heightSize; i++)
    {
        if (height[i] > highest)
        {
            higher = highest;
            higherIndex = highestIndex;
            highest = height[i];
            highestIndex = i;
        }
        else if (height[i] > higher)
        {
            higher = height[i];
            higherIndex = i;
        }
    }
    if (heightSize <= 2 || higherIndex < 0 || highestIndex < 0)
        return 0;
    ret = higher * (ABS(higherIndex - highestIndex) - 1);
    int left = MIN(higherIndex, highestIndex) + 1, right = MAX(higherIndex, highestIndex);
    for (i = left; i < right; i++)
        ret -= height[i];
    return ret + trap(height, left) + trap(height + right, heightSize - right);
}

评论