面试题 17.21. 直方图的水量

发表于 更新于 分类于 阅读次数： 本文字数： 975 阅读时长 ≈ 1 分钟

题目描述

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

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

题解

思路：当前位置能储存的水量取决于左右两边遇到的最大值中的最小值(min(leftTop, rightTop))。

方法：双指针。一个左指针，一个右指针。左指针小于右指针，当前位置可以存水，大小为leftTop-left，然后右移左指针，更新leftTop。同理，右指针小于左指针，当前位置可以存储rightTop-right的水量，左移右指针，更新rightTop。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int trap(int* height, int heightSize){
    if (heightSize < 3) return 0;   // 大小不足3，必定不能存水
    int lefttop = 0, righttop = heightSize - 1;
    while (lefttop+1 < heightSize && height[lefttop+1] >= height[lefttop]) lefttop++;
    while(righttop - 1 >= 0 && height[righttop-1] >= height[righttop]) righttop--;
    int left = lefttop, right = righttop, capacity = 0;
    while (left < right) {
        if (height[left] <= height[right]) {
            capacity += height[lefttop] - height[left];
            left++;
            if (height[left] > height[lefttop]) lefttop = left;
        } else if (height[left] > height[right]) {
            capacity += height[righttop] - height[right];
            right--;
            if (height[right] > height[righttop]) righttop = right;
        }
    }
    return capacity;  
}