[699. Falling Squares] C++ AC with brief explanation


  • 0

    We should divide the whole interval of the positions into different pieces. Because if we directly consider each whole interval, like:

    for this test case: [[50,47],[95,48],[88,77],[84,3],[53,87],[98,79],[88,28],[13,22],[53,73],[85,55]], when we add [84,3] into our graph, the heigh is changed from 47 to 50 only for the interval [84->87], not the whole interval.
    So from this, I think we should divide the whole interval by each start point and end point.

    In order to distinguish the start point and end point, I add 0.5 to the start point. So each time we add a new interval, we can easily find out all shorter intervals it affects. By finding out the largest height at the affected interval, we can figure out the new height for this interval and the new largest height for the whole graph.

    class Solution {
    public:
    vector<int> fallingSquares(vector<pair<int, int>>& positions) {
        if(positions.empty()) return {};
        int n = positions.size();
        vector<int> res;
        vector<double> intervals;
        for(auto p : positions){
            intervals.push_back(p.first + 0.5);
            intervals.push_back((p.first + p.second)*1.0);
        }
        sort(intervals.begin(), intervals.end());
        unordered_map<string, int> mp;
        vector<int> height(intervals.size(), 0);
        for(int i = 0; i < intervals.size(); ++i){
            mp[to_string(intervals[i])] = i;
        }
        int glb_max = 0;
        for(int i = 0; i < n; ++i){
            int left = mp[to_string(positions[i].first + 0.5)];
            int right = mp[to_string(positions[i].first*1.0 + positions[i].second)];
            int cur_max = *max_element(height.begin() + left, height.begin() + right + 1);
            while(left <= right){
                height[left++] = cur_max + positions[i].second;
            }
            glb_max = max(glb_max, cur_max + positions[i].second);
            res.push_back(glb_max);
        }
        return res;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.