[leetcode]659. Split Array into Consecutive Subsequences

Analysis

Happy girls day—— [每天刷题并不难0.0]

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Explanation:

Inspired by https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106516/Simple-C%2B%2B-Greedy-O(nlogn)-Solution-(with-explanation)

Implement

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, priority_queue<int, vector<int>, std::greater<int>>> tails;
        int num_3 = 0;
        for(int num:nums){
            if(!tails[num-1].empty()){
                int cnt = tails[num-1].top();
                tails[num-1].pop();
                tails[num].push(++cnt);
                if(cnt == 3)
                    num_3--;
            }
            else{
                tails[num].push(1);
                num_3++;
            }
        }
        return num_3==0;
    }
};