【题解】牛牛的和平年代

题意

我们定义一个整数可重集合是好的，当且仅当对于集合中任意两个元素 ，所有满足 的元素 c 都在集合中出现过。
现在，给你一个数组 mSet，你需要做的是，对于这个数组的每一个前缀，判断这个前缀是不是一个好的集合。所以，你将计算出的是一个数组，为布尔类型。

题解

题目到底想让我干啥？

在做这道题目之前，我们需要先转化一下题意。如同标题所说，这个好的集合，也就是类似一种元素连续的集合。任意两个元素之间都会被其他元素占满，说的就是在最大元素和最小元素之间的所有值，都可以在集合中取到。

我会暴力！

这简单，判断一个集合是不是好的简直太简单了。
因为在一个集合中元素的顺序是不重要的，我们可以随意打乱元素的顺序，那么按照递增或者递减的顺序来排列的元素一定是更有利于我们判断元素的相对大小的。
在一个已经排好序的集合里，这个集合现在可以说是一个列表了。那么这个列标显然有一个性质，那就是对于一个元素，排在左边的一定是不大于它的，排在右边的一定是不小于它的。
基于这个基本的认识，我们可以加以推广，来定义这个连续集合的概念。
一、单一元素的集合是连续的集合。
二、如果两个连续的集合是相邻的，那么整体也连续
所以我们也就因此找到了判断一个集合整体是否连续的方法，那就是在排序之后，任意在数组中相邻的元素的差值都不会超过1，也就是说他们之间是紧邻的，不可以插入另外的元素。

基于这个事实，我们就可以来编写我们的暴力程序了。我们将这个数组的每一个前缀都排好序，然后暴力扫描一遍，判断位置相邻的元素是不是值也相邻就好了。代码如下：

class Solution {
public:
    /**
     * 检查数组的每个前缀是不是一个好的集合
     * @param mSet int整型vector 
     * @return bool布尔型vector
     */
    vector<bool> continuousSet(vector<int>& mSet) {
        // write code here
        int n = mSet.size(), *tmp = new int[n];
        vector<bool>ans;
        for (int i = 0; i < n; i++) {
            tmp[i] = mSet[i];
            sort(tmp, tmp + i + 1);
            bool ok = true;
            for (int j = 0; j < i; j++)
                if (tmp[j] + 1 < tmp[j + 1])
                    ok = false;
            ans.push_back(ok);
        }
        return ans;
    }
};

当然，这样的代码时不可以通过这道题目的。因为在最坏情况下，我们需要对于每一个前缀从头到尾都扫描一遍，甚至排序一次。假设数组大小为 ，那么我们这样的时间复杂度就是 的，需要额外 的空间。虽然我们可以做一些小小的优化，比如把每次重新排序改成向有序数组中插入一个元素的插入排序，可以把时间复杂度降低到 ，但是依旧不可以通过此题。

你当我不会平衡树？

回想一下我们刚刚的需求，我们需要在每次插入新的元素之后，依旧获取一个有序的数组。为了达到这样的需求，我们直接弄一棵平衡树来维护这个排序数组，它不香么？更何况系统中的map，set等容器，全部都是以平衡树作为底层实现的东西，我们直接套用过来不就好了？

嗯，所以我们只需要把给前缀排序，修改成把数组的前缀元素，依次插入，形成一个前缀的平衡树就好了。但是我么你需要如何判断这个平衡树中的相邻元素都是相邻的呢？这时可能需要引入另外一个概念了。我们统计这个有序数组断开的地方的数量，如果断开的数量变成了0，那么我们就可以认为这个集合时连续的。

而做到这件事情，是非常容易的。考虑到每次只会新增加一个元素，那么我们只需要看看这个元素的添加会不会修改断开的地方的数量就好了。比如在元素 和元素 之间有一个断开，但是如果我们如果插入的元素是 ，我们会发现 和 连续，和 也连续，所以也就消除了一个断点。就此同理维护断点的数量，而且断点的数量也只会在新增元素的左右两侧发生改变，所以整体的时间复杂度就是 的，不过需要一个 空间复杂度为 的set来维护这个排序数组，已经可以通过此题。

我还有线性做法！

啥？你这还可以线性？光一个排序你都 了吧？吹啥牛呢？
嗯。。。确实，如果继续沿用上面的思路，是没办法绕过排序这个坎的。我们先把排序的问题放在一边，想想一些其他的线性数据结构，最好是支持 修改的。显然，很多高级的数据结构都不支持这个 修改。我们还得从最基本的数据结构入手。这大概就只能从数组和链表中做出选择了吧。
我们先看看，在不进行排序的前提下，我们可以对哪些前缀做出好坏的判断呢？
首先，第一个单元素的前缀一定是连续的。这个结论可以根据我们的定义得到。同时我们也可以从整体来进行考虑，一个集合是连续的，那么可以认为，在最大值和最小值之间的空隙，是全部都被填满了的。这样一个看似废话的话，却是优化的关键。这意味着，如果一个集合的值域范围，大于元素的个数，我们可以直接进行判断。而**一个值域范围比较小的集合，我们又是可以使用时间复杂度仅为 的基数排序的！**
这样，结合链表 的删除特性，我们可以直接将整个数组进行基数排序，然后倒序处理每个前缀，做到 的修改， 统计新的前缀的断点个数。
这样最终的时间复杂度就变成了 ，空间复杂度也是 。

代码

class Solution {
public:
    /**
     * 检查数组的每个前缀是不是一个好的集合
     * @param mSet int整型vector 
     * @return bool布尔型vector
     */
    vector<bool> continuousSet(vector<int>& mSet) {
        // write code here

        int n = mSet.size(), m = 1;
        vector<bool>ans(n);
        if (mSet.empty()) return ans;

        vector<int>pMax, pMin;
        pMax.push_back(mSet[0]);
        pMin.push_back(mSet[0]);

        for (int i = 1; i < n; i++) {
            pMax.push_back(max(pMax[i - 1], mSet[i]));
            pMin.push_back(min(pMin[i - 1], mSet[i]));
            if (0ll + pMax[i] - pMin[i] <= 0ll + i) m = i + 1;
        }

        for (int i = m; i < n; i++) ans[i] = false;

        struct Node {
            Node *last, *next;
            int value;
            int cnt;
            Node() {
                last = next = NULL;
                cnt = 0;
            }
        };

        int Min = pMin[m - 1];
        int Max = pMax[m - 1];
        vector<Node>node(Max - Min + 1);

        for (int i = 0; i < m; i++) 
            node[mSet[i] - Min].cnt++;

        Node head, tail;
        head.next = &tail;
        tail.last = &head;

        for (int v = Min; v <= Max; v++) {
            node[v - Min].value = v;
            if (v != Min) node[v - Min].last = &node[v - Min - 1];
            else node[v - Min].last = &head, head.next = &node[v - Min];
            if (v != Max) node[v - Min].next = &node[v - Min + 1];
            else node[v - Min].next = &tail, tail.last = &node[v - Min];
        }

        for (Node *cur = head.next; cur != &tail; cur = cur->next) 
            if (cur->cnt == 0) {
                cur->last->next = cur->next;
                cur->next->last = cur->last;
            }

        int cnt = 0;
        for (Node *cur = head.next; cur != &tail; cur = cur->next) {
            cnt++;
            if (cur->last != &head && cur->value - 1 == cur->last->value) 
                cnt--;
        }

        for (int i = m - 1; i >= 0; i--) {
            if (cnt == 1) {
                ans[i] = true;
            } else {
                ans[i] = false;
            }
            if (!--node[mSet[i] - Min].cnt) {
                Node *cur = &node[mSet[i] - Min];
                cur->next->last = cur->last;
                cur->last->next = cur->next;
                cnt--;
                if (cur->last != &head && cur->value - 1 == cur->last->value)
                    cnt++;
                if (cur->next != &tail && cur->value + 1 == cur->next->value)
                    cnt++;
            }
        }
        return ans;
    }
};