有意思的数学题：Trapping Rain Water

LeetCode传送门 https://leetcode.com/problems/trapping-rain-water/

 

 

目标：找出积木能容纳的水的“面积”，如图中黑色部分是积木，蓝色为可容纳水的部分

假设：积木宽度均为1

输入：各个积木的高度

输出：所有积木能容纳水的“面积”

 

思考过程

1. 逐一求积木的间隔似乎不太容易。特别对于图中3-7积木间的容积，如果可以先求底部（4-6间）的容积，当求解上层（3-7）的容积时，还需要做额外的处理，如减掉底部的高度。

2. 既然如此，可否先求出3-7间整体的容积，再将两积木之间的积木面积（4、5、6）减去，即可得这个区域的容积？

3. 那么问题转换成了，已知一个积木，如何寻找下一个积木，并计算这个两积木间的容积

4. 尝试一，寻找一个至少不比当前积木低的积木，作为下一个积木，如图例子为当前积木3，下一个积木7。那么之间的容积如何计算呢，简单，积木3的高度乘以两积木间的间隔宽度，再减去，积木3与积木7之间的积木（4、5、6）面积。

5. 问题：下次迭代从何开始？上一个例子，可以从积木7继续算起。然而如果找不到相应的积木呢，那么从积木3的下一个积木4开始。

6. 看起来，似乎正确。于是乎，开始写代码了。然而第一次提交就献给了WA（/(ㄒoㄒ)/~~）

7. 错误的情况，如果当前的积木是一个特别高的积木，后继找不到更高的积木，然而实际上之间是可能有容积的！不赘述了，补救思路是：在寻找更高的积木的同时，记录当前找到的最高的积木。如果没有找到更高的积木，使用当前找到的最高的积木作为下一个积木，并计算容积。

 

思路总结

迭代的过程

1. 寻找下一个至少不比当前积木低的积木，寻找的同时，记录当前找到的最高的积木高度

2. 如果找到，则计算两积木之间的容积（计算过程见思考过程2）

3. 如果没有找到，则计算当前积木与当前找到的最高的积木之间的容积

4. 当前积木设置为找到的积木（可能是2或3的情况），继续迭代

 

时间复杂度

O(n)

 

代码实现

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() == 0) {
            return 0;
        }

        int water = 0;
        int preIndex = 0;
        int preHeight = 0;

        // 找到第一个高度非0的bar
        while (preIndex < height.size() - 1 && height[preIndex] == 0) {
            ++preIndex;
        }

        if (preIndex == height.size() - 1) {
            return 0;
        }

        // 遍历
        while (preIndex < height.size()) {
            preHeight = height[preIndex];

            // 寻找更高的或相等的bar
            // 同时记录遍历过的最高的bar
            // 如果寻找不到更高的或相等的bar时，使用记录值计算
            int next = preIndex + 1;
            int minHeight = 0;
            int minIndex = next;

            while (next < height.size() && height[next] < preHeight) {
                if (height[next] > minHeight) {
                    minHeight = height[next];
                    minIndex = next;
                }
                ++next;
            }

            // 如果找到
            if (next != height.size()) {
                water += (preHeight * (next - preIndex - 1)); // 计算总面积

                for (int i = preIndex + 1; i < next; ++i) { // 减去中间bar面积
                    water -= height[i];
                }

                preIndex = next; // 从找到的bar开始下一次的迭代
            } else {
                water += (minHeight * (minIndex - preIndex - 1)); // 计算总面积

                for (int i = preIndex + 1; i < minIndex; ++i) { // 减去中间bar面积
                    water -= height[i];
                }

                preIndex = minIndex; // 从次高的bar开始
            }
        }

        return water;
    }
};

int main(int argc, char const *argv[]) {
    Solution solution;
    vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << solution.trap(height) << endl;
    return 0;
}

 

闲聊一二

大年初一！祝大家猴年快乐啦，已经工作的童鞋升职加薪，要实习、找工作的童鞋offer多多~博主今年也要面对找实习、找工作的人生大事儿了。好久没写博客了，默默的哀悼上个学期，自己瞎折腾，弄出的不成熟的东西。希望猴年是激情，奋斗，收获的一年~

 

ps：有没有对我感兴趣的boss收留~附交友地址一枚https://github.com/zrss

简单粗暴的resume：https://github.com/zrss/ghostblog，近期再修改下