题目分析

题目有一定的难度，用到了贪心的思路，一般来说贪心算法的题目都是比较难的，因为很难想到为什么当前最优解一定是局部最优解，而且需要数学去证明才能够保证贪心法是正确的。

堆+贪心

我们考虑1，2，3，3，4，5这个情况，当出现1的时候，我们发现前面没有以0结尾的数组，因此我们要单独建立一个数组以1开头，1结尾，长度为1。当出现2的时候，我们发现前面有以1结尾的数组，这时面临一个选择。是重新开辟一个以2开头，2结尾，长度为1的数组呢？还是在以1结尾的数组中添加元素2，变成以2结尾，长度为2的数组呢？我们发现添加元素一定是最优的。因为如果创建一个数组，以2为开头，如果得到了最优分配方式，那么将以2为开头的数组添加在以1结尾的数组中也一定是最优的。

以上面的规则我们继续看，当出现第一个3时，也是将3添加到以2为结尾的数组后面，形成了以3结尾长度为3的数组。当出现第二个3时，没有以2结尾的数组了，这时要重新开辟一个以3结尾，长度为1的数组。当出现4时，又面临选择了，有两个以3结尾的数组，是选择添加哪一个数组的尾部呢？选择添加最短的，因为添加在最长的满足最优解的情况下，添加在最短的也一定满足最优解。这也体现了一个贪心思想。

因此堆的思想就体现出来了，我们维护一个最小堆即可，记录以k结尾的数组的长度。每次将最短的一个拿出来。

算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<functional>

using namespace std;

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> m;
        for (int x : nums) {
            if (m[x].empty()) m[x] = priority_queue<int, vector<int>, greater<int>>();
            if (m.find(x - 1) == m.end()) {
                m[x].push(1);
            }
            else {
                int length = m[x - 1].top();
                m[x - 1].pop();
                if (m[x - 1].empty()) m.erase(x - 1);
                m[x].push(length + 1);
            }
        }
        for (auto tail : m) {
            if (tail.second.top() < 3) return false;
        }
        return true;
    }
};

哈希表优化+贪心

堆的时间复杂度log(n)，我们还可以继续优化，使用常数级的哈希表查找即可。

**用count哈希表先统计每个元素出现的次数，然后遍历整个数组，还以1，2，3，3，4，5为例，先统计1出现1次，2出现1次，3出现2次，4出现1次，5出现1次。然后遍历数组，开始遍历到1，如果1还存在，那么要看是否有以0结尾的数组，即tail[0]是否等于0，如果有，则tail[0]–, tail[1]++, count[x]–。如果没有要建立一个长度为3的数组，如果count[2]和count[3]都大于0则可以建立，否则直接return false。可以建立时，count[1]–, count[2]–,count[3]–,tail[3]++**，此时说明花费了1，2，3这三个数，建立了一个以3结尾的数组。然后遍历到2的时候，因为count[2]–以后，count[2] = 0，因此直接跳过。同理，第一个3也直接跳过。到第二个3时，因为没有以2结尾的数组，因此又建立了一个以5结尾的数组。遍历到4和5时，因为创建5结尾的数组时，count[4]–, count[5]–，也都直接跳过。最终return true。

小伙伴们想一想为什么这里时间复杂度会缩短呢？因为我们直接建立一个长度为3的数组，不需要取出最短的，哪一个都满足条件，不需要像上面一样，要优先在最短的数组中添加，满足长度条件。这里如果无法建立长度为3的数组则直接return false。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> count, tail;
        for (int x : nums) count[x]++;
        for (int x : nums) {
            if (count[x] > 0) {
                if (tail[x - 1] != 0) {
                    tail[x - 1]--;
                    tail[x]++;
                    count[x]--;
                }
                else {
                    if (count[x + 1] && count[x + 2]) {
                        count[x]--;
                        count[x + 1]--;
                        count[x + 2]--;
                        tail[x + 2]++;
                    }
                    else return false;
                }
            }
        }
        return true;
    }
};

刷题总结

贪心题目做不出来不要灰心，多见一见题目，可能面试中就会遇到原题。在字节，滴滴等公式面试时，我就遇到了许多原题。小伙伴们想找好工作的，赶紧刷起来。