LeetCode 区间链表问题

1562. 查找大小为 M 的最新分组

class Solution {
public:
    vector<int>l,r;
    
    int get(int x){
        return r[x]-x+1;
    }
    
    int findLatestStep(vector<int>& arr, int m) {
        int n=arr.size();
        l=vector<int>(n+2),r=vector<int>(n+2);
        
        int cnt=0;
        int res=-1;
        for(int i=0;i<n;i++){
            int x=arr[i];
            
            if(l[x-1] && r[x+1]){
                if(get(l[x-1])==m)cnt--;
                if(get(x+1)==m)cnt--;
                
                r[l[x-1]]=r[x+1];
                l[r[x+1]]=l[x-1];
                
                if(get(l[x-1])==m)cnt++;
                
            }else if(l[x-1]){
                if(get(l[x-1])==m)cnt--;
                
                r[l[x-1]]=x;
                l[x]=l[x-1];
                
                if(get(l[x-1])==m)cnt++;
            }else if(r[x+1]){
                if(get(x+1)==m)cnt--;
                
                l[r[x+1]]=x;
                r[x]=r[x+1];
                if(get(x)==m)cnt++;
            }else{
                l[x]=r[x]=x;
                if(get(x)==m)cnt++;
            }
            if(cnt)res=i+1;
        }
                
        return res;
    }
};

352. 将数据流变为多个不相交区间

class SummaryRanges {
public:
    /** Initialize your data structure here. */
    map<int, int> l, r;

    SummaryRanges() {

    }

    void addNum(int val) {
        if (r.size()) {
            auto it = r.upper_bound(val);
            if (it != r.begin()) {
                --it;
                if (it->second >= val) return;
            }
        }
        int right = r.count(val + 1), left = l.count(val - 1);
        if (left && right) {
            r[l[val - 1]] = r[val + 1];
            l[r[val + 1]] = l[val - 1];
            r.erase(val + 1), l.erase(val - 1);
        } else if (right) {
            l[r[val + 1]] = val;
            r[val] = r[val + 1];
            r.erase(val + 1);
        } else if (left) {
            r[l[val - 1]] = val;
            l[val] = l[val - 1];
            l.erase(val - 1);
        } else {
            r[val] = val;
            l[val] = val;
        }
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> res;
        for (auto i:r) {
            int left = i.first, right = i.second;
            res.push_back({left, right});
        }
        return res;
    }
};