699. Falling Squares

问题：

无限横坐标中，下落正方块问题。

position[i]={x, len}

表示：每次落在坐标 x 的位置，正方块变长len。

求每次落下后，当前最高y坐标的高度。

Example 1:
Input: [[1, 2], [2, 3], [6, 1]]
Output: [2, 5, 5]
Explanation:
After the first drop of positions[0] = [1, 2]: _aa _aa ------- The maximum height of any square is 2.

After the second drop of positions[1] = [2, 3]: __aaa __aaa __aaa _aa__ _aa__ -------------- The maximum height of any square is 5. The larger square stays on top of the smaller square despite where its center of gravity is, because squares are infinitely sticky on their bottom edge.

After the third drop of positions[1] = [6, 1]: __aaa __aaa __aaa _aa _aa___a -------------- The maximum height of any square is still 5. Thus, we return an answer of [2, 5, 5].


Example 2:
Input: [[100, 100], [200, 100]]
Output: [100, 100]
Explanation: Adjacent squares don't get stuck prematurely - only their bottom edge can stick to surfaces.
 
Note:
1 <= positions.length <= 1000.
1 <= positions[i][0] <= 10^8.
1 <= positions[i][1] <= 10^6.

　　

解法：map区段法

思路：

• 使用map，这种已经排序的结构体存储当前下落后的坐标状态。sq: {key: [start, end], value: height}
  • 按照start排序
• 对于每次落下的cur=position[i]
  • 在map中sc_cmp找到与之cur相交的x区段。
    • sc_cmp.start ：范围：
      • lower_bound(cur.start) - 1 ～  > cur.end
  • 在这个区段中
    • 两边界相交part
      • 删除
      • 新规保存，遍历完后追加用：bound2:
        • 区间变化：
          • 左边：end->cur.start
          • 右边：start->cur.end
        • 高度：
          • 原高度不变：sc_cmp.height
    • 完全真包含part
      • 删除
      • 完全用新落下的方块替代，遍历完后追加
        • 区间不变：新方块.start ～ 新方块.end
        • 高度：
          • 新方块.height+这个区段中的最高高度：base_h（这个值需要遍历完区段，不断求max得到）
  • 遍历完区段后
    • 追加更新后的区间part
      • 两边界相交part：bound2
      • 完全真包含part：新落下的方块
    • res[i]= max(当前落下后更新的高度，maxH)

代码参考：

class Solution {
public:
    struct Sec{
        int start;
        int end;
        int height;
        Sec(int s, int e, int h):start(s), end(e), height(h) {};
    };
    
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        vector<int> res;
        map<pair<int, int>, int> sq;
        int maxH = INT_MIN;
        for(auto p:positions) {
            //find the intersecting part
            //[start~end): [p[0], p[0]+p[1])
            //height: p[1]
            Sec cur(p[0], p[0]+p[1], p[1]);
            auto it = sq.lower_bound({cur.start, cur.end});
            vector<Sec> bound2;//start,end
            int base_h = 0;
            if(it!=sq.begin()) it--;
            //check the intersecting part:
            //1. to get the base max height;
            //2. erase all intersected section.
            //3. memo the 2 bounds section.(for following appending)
            while(it!=sq.end()) {
                Sec sc_cmp(it->first.first, it->first.second, it->second);
                //over 2 bounds:
                if(sc_cmp.end<=cur.start) {
                    it++;
                    continue;
                }
                if(sc_cmp.start>=cur.end) break;
                //2 bounds:
                //left
                if(sc_cmp.start<cur.start)
                    bound2.emplace_back(Sec(sc_cmp.start, cur.start, sc_cmp.height));
                //right
                if(sc_cmp.end>cur.end)
                    bound2.emplace_back(Sec(cur.end, sc_cmp.end, sc_cmp.height));
                base_h = max(base_h, sc_cmp.height);
                it = sq.erase(it);//cause erase action, it may be the next item.
            }
            //append:
            //2 bounds +  cur section
            sq[{cur.start, cur.end}] = base_h + cur.height;
            for(auto b:bound2) {
                sq[{b.start, b.end}] = b.height;
            }
            //cout<<"cur_height:"<<base_h + cur.height<<endl;
            maxH = max(maxH, base_h + cur.height);
            res.push_back(maxH);
        }
        return res;
    }
};