Given_n_non-negative integers representing an elevation map where the width of each bar is1, compute how much water it is able to trap after raining.

Have you met this question in a real interview?

Yes

Example

Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

Challenge

O(n) time and O(1) memory

O(n) time and O(n) memory is also acceptable.

class Solution {
public:
    /**
     * @param heights: a vector of integers
     * @return: a integer
     */
    int trapRainWater(vector<int> &heights) {
        // write your code here
        int res = 0;
        if (heights.empty()) {
            return 0;
        }
        int left = 0, right = heights.size() - 1;
        int l = heights[left];
        int r = heights[right];
        while (left < right) {
            if (l < r) {
                ++left;
                res += max(l - heights[left], 0);
                l = max(l, heights[left]);
            } else {
                --right;
                res += max(r - heights[right], 0);
                r = max(r, heights[right]);
            }
        }

        return res;
    }
};


class Solution {
public:
    /**
     * @param heights: a vector of integers
     * @return: a integer
     */
    int trapRainWater(vector<int> &heights) {
        // write your code here
        int water = 0;
        if (heights.size() < 3) {
            return 0;
        }
        vector<int> leftHeight(heights.size(), 0);
        vector<int> rightHeight(heights.size(), 0);
        leftHeight[0] = heights[0];
        for (int i = 1; i < heights.size(); ++i) {
            leftHeight[i] = max(leftHeight[i-1], heights[i]);
        }
        rightHeight[heights.size()-1] = heights[heights.size()-1];
        for (int j = heights.size()-2; j >= 0; --j) {
            rightHeight[j] = max(rightHeight[j+1], heights[j]);
        }
        for (int i = 1; i < heights.size(); ++i) {
            water += min(leftHeight[i], rightHeight[i]) - heights[i];
        }
        return water;
    }
};

class Solution {
public:
    /**
     * @param heights: a vector of integers
     * @return: a integer
     */
    int trapRainWater(vector<int> &heights) {
        // write your code here
        int left = 0, right = heights.size()-1;
        int water = 0;
        int smaller = 0;
        while (left < right) {
            if (heights[left] < heights[right]) {
                smaller = heights[left];
                while (left < right && heights[left] <= smaller) {
                    water += smaller - heights[left];
                    ++left;
                }
            } else {
                smaller = heights[right];
                while (left < right && heights[right] <= smaller) {
                    water += smaller - heights[right];
                    --right;
                }
            }
        }
        return water;
    }
};

class Solution {
public:
    /**
     * @param heights: a vector of integers
     * @return: a integer
     */
    int trapRainWater(vector<int> &heights) {
        // write your code here
        int res = 0;
        if (heights.empty()) {
            return 0;
        }
        int left = 0, right = heights.size() - 1;
        int l = heights[left];
        int r = heights[right];
        while (left < right) {
            if (l < r) {
                ++left;
                if (heights[left] < l) {
                    res += l - heights[left];
                } else {
                    l = heights[left];
                }
            } else {
                --right;
                if (heights[right] < r) {
                    res += r - heights[right];
                } else {
                    r = heights[right];
                }
            }
        }

        return res;
    }
};

results matching ""

    No results matching ""