解法：二分 & 贪心

求最小值最大，容易想到二分答案。接下来思考如何确定二分值 $V$ 是否有效。

我们可以用一个滑动窗口从左到右计算每个城市的电量。若当前城市电量不足，我们需要新建供电站补上。由于左边的城市的电量都大于等于 $V$，因此新的供电站应该尽量建在右边。显然这些供电站应该建在滑动窗口内部的最右侧。

二分答案后模拟以上过程即可。复杂度 $\mathcal{O}(n\log (nA + k))$，其中 $A$ 是 stations[i] 的最大值。

参考代码（c++）

###c++

class Solution {
public:
    long long maxPower(vector<int>& stations, int R, int K) {
        int n = stations.size();

        auto check = [&](long long LIM) {
            vector<long long> vec;
            for (int x : stations) vec.push_back(x);

            // 初始化滑动窗口的和
            long long sm = 0;
            for (int i = 0; i <= R && i < n; i++) sm += vec[i];
            
            // 表示还有几个供电站可以新建
            long long rem = K;
            // 从左到右计算每个城市的电量，同时维护滑动窗口 [l, r]
            for (int i = 0, l = 0, r = R; ; i++) {
                if (sm < LIM) {
                    // 当前城市电量不足
                    long long delta = LIM - sm;
                    // 新供电站不够，返回 false
                    if (delta > rem) return false;
                    // 新供电站足够，建在滑动窗口最右边
                    rem -= delta;
                    vec[r] += delta;
                    sm += delta;
                }
                if (i == n - 1) break;

                // 滑动窗口向前移动一个城市
                if (i >= R) sm -= vec[l], l++;
                if (r != n - 1) sm += vec[r + 1], r++;
            }
            return true;
        };

        // 二分答案
        long long head = 0, tail = 2e10;
        while (head < tail) {
            long long mid = (head + tail + 1) >> 1;
            if (check(mid)) head = mid;
            else tail = mid - 1;
        }
        return head;
    }
};

解法：并查集 & 数据结构

首先用并查集计算每个电站属于哪些电网，然后对每个电网用一个 set 维护当前在线的电站，这样即可在 $\mathcal{O}(\log n)$ 的复杂度内删除电站，并在 $\mathcal{O}(1)$ 的复杂度内查询编号最小的在线电站。

整体复杂度 $\mathcal{O}((n + q)\log n)$。

参考代码（c++）

class Solution {
public:
    vector<int> processQueries(int n, vector<vector<int>>& connections, vector<vector<int>>& queries) {
        int root[n + 1];
        // 求并查集的根
        auto findroot = [&](this auto &&findroot, int x) -> int {
            if (root[x] != x) root[x] = findroot(root[x]);
            return root[x];
        };

        // 构建电网
        for (int i = 1; i <= n; i++) root[i] = i;
        for (auto &edge : connections) {
            int x = findroot(edge[0]), y = findroot(edge[1]);
            if (x != y) root[x] = y;
        }

        // 对每个电网用一个 set 维护当前在线的电站
        set<int> st[n + 1];
        for (int i = 1; i <= n; i++) st[findroot(i)].insert(i);

        vector<int> ans;
        for (auto &qry : queries) {
            int r = findroot(qry[1]);
            if (qry[0] == 1) {
                // 该电站未离线
                if (st[r].count(qry[1])) ans.push_back(qry[1]);
                // 该电站已离线，但电网里还有未离线的电站，取最小值
                else if (st[r].size() > 0) ans.push_back(*st[r].begin());
                // 电网里的电站都离线了
                else ans.push_back(-1);
            } else {
                // 将电站离线
                st[r].erase(qry[1]);
            }
        }
        return ans;
    }
};

解法：对顶堆

我们简单改写一下题意：在长度为 $k$ 的滑动窗口中，求出现次数前 $x$ 大的元素之和。

设 $(c_v, v)$ 表示元素 $v$ 的频率和值，我们其实就需要一个数据结构，求前 $x$ 大的 pair 的 $c_v \times v$ 之和。那么这种数据元素需要支持哪些操作呢？

考虑滑动窗口从 $[i, i + k - 1]$ 滑动到 $[i + 1, i + k]$ 会发生什么。其实就是从数据元素中删除了 $(c_{a_i}, a_i)$ 和 $(c_{a_{i + k}}, a_{i + k})$ 这两个 pair，又新增了 $(c_{a_i} - 1, a_i)$ 和 $(c_{a_{i + k}} + 1, a_{i + k})$ 这两个 pair。因此这个数据元素要支持这些操作：

• 加入一个元素
• 删除一个元素
• 求前 $k$ 大元素的和

这就是经典的对顶堆（因为需要删除元素，其实是对顶 multiset），详见 leetcode 295. 数据流的中位数。复杂度 $\mathcal{O}(n\log n)$。

参考代码（c++）

###cpp

// 对顶堆模板开始，注意以下模板维护的其实是前 K 小的元素

struct Magic {
    int K;
    typedef pair<int, int> pii;
    multiset<pii> st1, st2;
    long long sm1;

    Magic(int K): K(K) {
        sm1 = 0;
    }

    // 把第一个堆的大小调整成 K
    void adjust() {
        while (!st2.empty() && st1.size() < K) {
            pii p = *(st2.begin());
            st1.insert(p); sm1 += 1LL * p.first * p.second;
            st2.erase(st2.begin());
        }
        while (st1.size() > K) {
            pii p = *prev(st1.end());
            st2.insert(p);
            st1.erase(prev(st1.end())); sm1 -= 1LL * p.first * p.second;
        }
    }

    // 加入元素 p
    void add(pii p) {
        if (!st2.empty() && p >= *(st2.begin())) st2.insert(p);
        else st1.insert(p), sm1 += 1LL * p.first * p.second;
        adjust();
    }

    // 删除元素 p
    void del(pii p) {
        auto it = st1.find(p);
        if (it != st1.end()) st1.erase(it), sm1 -= 1LL * p.first * p.second;
        else st2.erase(st2.find(p));
        adjust();
    }
};

// 对顶堆模板结束

class Solution {
public:
    vector<long long> findXSum(vector<int>& nums, int k, int x) {
        int n = nums.size();
        vector<long long> ans;
        unordered_map<int, int> cnt;
        Magic magic(x);
        for (int i = 0; i < k; i++) cnt[nums[i]]++;
        // 因为模板维护的是前 x 小的元素，所以这里元素全部取反
        for (auto &p : cnt) magic.add({-p.second, -p.first});
        for (int i = 0; ; i++) {
            ans.push_back(magic.sm1);
            if (i + k == n) break;
            // 滑动窗口滑动一格
            magic.del({-cnt[nums[i]], -nums[i]});
            cnt[nums[i]]--;
            if (cnt[nums[i]] > 0) magic.add({-cnt[nums[i]], -nums[i]});
            if (cnt[nums[i + k]] > 0) magic.del({-cnt[nums[i + k]], -nums[i + k]});
            cnt[nums[i + k]]++;
            magic.add({-cnt[nums[i + k]], -nums[i + k]});
        }
        return ans;
    }
};

解法：模拟

不会有人链表题真的去操作原链表吧？把链表里的数提取出来，按题意算出答案后新建一个链表即可。复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        // 按题意模拟
        unordered_set<int> st;
        for (int x : nums) st.insert(x);
        vector<int> vec;
        for (; head != nullptr; head = head->next) if (st.count(head->val) == 0) vec.push_back(head->val);

        // 根据答案 vec 中新建一个链表
        ListNode *dummy = new ListNode(), *now = dummy;
        for (int x : vec) {
            now->next = new ListNode(x);
            now = now->next;
        }
        return dummy->next;
    }
};

解法：模拟

数据范围很小，模拟即可。复杂度 $\mathcal{O}(n^2)$。

参考代码（c++）

class Solution {
public:
    bool hasSameDigits(string s) {
        while (s.size() > 2) {
            string t;
            for (int i = 0; i + 1 < s.size(); i++) {
                int x = s[i] - '0', y = s[i + 1] - '0';
                t.push_back((x + y) % 10 + '0');
            }
            s = t;
        }
        return s[0] == s[1];
    }
};

解法：枚举

如果最后的众数是 $x$，那么答案就是 $c_x + \min(m, \sum\limits_{x - k \le i \le x + k, i \ne x} c_i)$，其中 $c_x$ 是 nums 里 $x$ 的数量，$m$ 是操作次数。

这个式子的值会随着 $x$ 的变化发生怎样的改变？$c_x$ 肯定在 $x$ 取到 nums 里有的数时才尽可能大，而 $\sum\limits_{x - k \le i \le x + k, i \ne x} c_i$ 的值和 $x$ 被几个数的“范围”覆盖到有关。一个数 $x$ 能覆盖的范围是 $[x - k, x + k]$，当 $x$ 增加到某个区间的左端点时，被覆盖到的数量会增加 $1$，之后在区间中间不发生变化。

所以我们只要考虑 $x$ 取 nums 中出现的数，以及它们 $-k$，共 $2n$ 种数。$\sum$ 的值可以用二分的方式快速计算。复杂度 $\mathcal{O}(n\log n)$。

参考代码（c++）

###cpp

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        // 把所有要考虑的值放进 set 里
        unordered_set<int> st;
        // 统计 nums 里每种数出现了几次
        unordered_map<int, int> mp;
        for (int x : nums) {
            st.insert(x); st.insert(x - k);
            mp[x]++;
        }

        // 给 nums 排序，方便接下来二分计数。
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int x : st) {
            int tmp = 0;
            // 二分计算 (x, x + k] 里有几个数
            tmp += upper_bound(nums.begin(), nums.end(), x + k) - upper_bound(nums.begin(), nums.end(), x);
            // 二分计算 [x - k, x) 里有几个数
            tmp += lower_bound(nums.begin(), nums.end(), x) - lower_bound(nums.begin(), nums.end(), x - k);
            tmp = min(tmp, numOperations);
            ans = max(ans, mp[x] + tmp);
        }
        return ans;
    }
};

解法：贪心

思维第一步

看到“任一元素加上或减去 value”，而且“可以操作任意次”，马上反馈出等价条件：

数 $x$ 可以变成任意满足 y mod value == x mod value 的数 $y$。

因此，我们可以把整个序列按元素取模的值分成 value 类，每一类元素都不会因为操作而变成其他类别里的元素。

思维第二步

既然我们要让“缺失的最小非负整数”最大，设第 $i$ 类里有 $k$ 个数，那么它们需要变成 $i, v + i, 2v + i, \cdots (k - 1)v + i$ 才能让 mex 尽可能大。

举个例子帮助大家理解，假设 $v = 5$，第 $2$ 类里有 $3$ 个数，那么它们需要变成 $2, 7, 12$ 才能让 mex 尽可能大。如果变成别的，比如 $2, 12, 17$，那因为缺失了 $7$（而且其他类别的数也没法变成 $7$），那 mex 至多就是 $7$ 了。如果是 $2, 7, 12$，那 mex 还有可能是 $17$，肯定这样做更优。

最终处理

既然我们已经确定了每个数都要变成什么，那完成变化以后，直接计算变化后序列的 mex 就是答案。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###c++

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int v) {
        int n = nums.size();
        // vis[i] 表示变化后的序列里是否出现过元素 i
        // 答案肯定不超过 n
        // 因为最好情况就是 nums = [0, 1, ..., n - 1]，这样 mex = n
        bool vis[n + 1];
        memset(vis, 0, sizeof(vis));
        
        // cnt[i] 表示第 i 类元素目前有几个
        int cnt[v];
        memset(cnt, 0, sizeof(cnt));
        for (int x : nums) {
            // t 是元素 x 所属的类别
            int t = (x % v + v) % v;
            // y 是元素 x 应该变成什么数
            int y = cnt[t] * v + t;
            if (y < n) vis[y] = true;
            cnt[t]++;
        }
        
        // 计算变化后序列的 mex
        for (int i = 0; i <= n; i++) if (!vis[i]) return i;
        return -1;
    }
};

解法：枚举

这种一前一后两个子数组的题，一般考虑枚举分界点（比如第二个子数组的开头）。

维护 $f(i)$ 表示以第 $i$ 个元素为结尾，最长的单调递增子数组是多长；$g(i)$ 表示以第 $i$ 个元素为开头，最长的单调递增子数组是多长。那么我们枚举第二个子数组的开头 $b$，说明第一个子数组的结尾就是 $(b - 1)$，答案就是 $\max(\min(f(b - 1), g(b)))$。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###cpp

class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        int n = nums.size();
        int f[n + 2], g[n + 2];
        f[0] = 0; g[n + 1] = 0;
        // 计算以第 i 个元素为结尾，最长的单调递增子数组是多长
        for (int i = 1; i <= n; i++) {
            if (i > 1 && nums[i - 2] < nums[i - 1]) f[i] = f[i - 1] + 1;
            else f[i] = 1;
        }
        // 计算以第 i 个元素为开头，最长的单调递增子数组是多长
        for (int i = n; i > 0; i--) {
            if (i < n && nums[i - 1] < nums[i]) g[i] = g[i + 1] + 1;
            else g[i] = 1;
        }
        int ans = 0;
        // 枚举第二个子数组的开头
        for (int i = 1; i <= n; i++) ans = max(ans, min(f[i - 1], g[i]));
        return ans;
    }
};

解法：DP

设 $f(i, j)$ 表示巫师 $j$ 完成药水 $i$ 的时间，且暂时不考虑这瓶药水后面的步骤。这个时间受到三个限制：

1. 巫师 $(j - 1)$ 需要先完成这个药水，巫师 $j$ 才能开始酿造，即 $f(i, j) \xleftarrow{\max} f(i, j - 1) + s_jm_i$。
2. 巫师 $j$ 需要先完成上一瓶药水才能开始酿造，即 $f(i, j) \xleftarrow{\max} f(i - 1, j) + s_jm_i$。
3. 巫师 $j$ 完成这瓶药水时，巫师 $(j + 1)$ 也要完成上一瓶药水，即 $f(i, j) \xleftarrow{\max} f(i - 1, j + 1)$。

这样我们就能算出巫师 $n$ 完成药水 $i$ 的时间。注意，由于 $f(i, j)$ 没有考虑这瓶药水后面的步骤，所以可能会出现 $f(i, j) + s_{j + 1}m_i < f(i, j + 1)$ 的情况。因此我们还要从 $f(i, n)$ 开始倒推，计算 $f(i, j) = f(i, j + 1) - s_{j + 1}m_i$，把每名巫师真实的完成时间算出来。

复杂度 $\mathcal{O}(nm)$。

参考代码（c++）

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size(), m = mana.size();

        // 空间优化：去掉了 DP 的第一维
        long long f[n + 2];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= m; i++) {
            // 正推计算巫师 j 完成药水 i，且不考虑后面步骤的时间
            for (int j = 1; j <= n; j++) f[j] = max(max(f[j - 1], f[j]) + skill[j - 1] * mana[i - 1], f[j + 1]);
            // 倒推计算巫师 j 完成药水 i 的真实时间
            for (int j = n - 1; j > 0; j--) f[j] = f[j + 1] - skill[j] * mana[i - 1];
        }

        return f[n];
    }
};

解法 1：模拟

按题意模拟即可，复杂度 $\mathcal{O}(n^2)$。

参考代码（c++）

###c++

class Solution {
public:
    int triangularSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> f[2];
        f[0] = f[1] = vector<int>(n);
        f[n & 1] = nums;
        for (int i = n; i > 1; i--) for (int j = 0; j + 1 < i; j++) f[i & 1 ^ 1][j] = (f[i & 1][j] + f[i & 1][j + 1]) % 10;
        return f[1][0];
    }
};

解法 2：数学

考虑第 $i$（从 $0$ 开始）个数对答案的贡献，其实就是 $C_{n-1}^i$。由于模数不是质数，通过 扩展卢卡斯定理 求出所有组合数，答案就是 $\sum\limits_{i=0}^{n-1} C_{n-1}^i \times \text{nums[i]}$。复杂度 $\mathcal{O(n\log m)}$，其中 $m$ 是模数。