Water land - Airbnb

airbnb面试题汇总

water land。 比如terrian是[3,2,1,2] print出来就是

*

* *   *

* * * *

* * * *

然后给你一个dumpPoint，一个waterAmount，比如dumpPoint 1, waterAmount 2，因为有重力，所以是从index 2开始加水

*

* * w *

* * * *

* * * *

terrian两边是最高，模拟，先向左找到非递增的最低点，如果该点和dumpPoint一样高，往右继续找非递增的最低点，如果一样高就放到dumpPoint，不一样的话放置在非递增的最低点

void getWaterLevel(vector<int> &height, int position, int count) {
    if(height.empty()) return;
    const int n = height.size();
    vector<int> water(n, 0);
    while(count--) {
        int putLocation = position;
        int left = position, right = position;
        while(left >= 1) {
            if(height[left - 1] + water[left - 1] > height[left] + water[left]) break;
            --left;
        }
        if(height[left] + water[left] < height[position] + water[position])
            putLocation = left;
        else {
            while(right < n - 1) {
                if(height[right + 1] + water[right + 1] > height[right] + water[right]) break;
                ++right;
            }
            if(height[right] + water[right] < height[position] + water[position])
                putLocation = right;
        }
        water[putLocation]++;
    }

    int highest = 0;
    for(int i = 0; i < n; ++i)
        if(height[i] + water[i] > highest)
            highest = height[i] + water[i];
    for(int h = highest; h >= 1; --h) {
        for(int i = 0; i < n; ++i) {
            if(height[i] + water[i] < h) cout<<" ";
            else if(height[i] < h) cout<<"w";
            else cout<<"*";
        }
        cout<<endl;
    }
}