题目描述

麻将的游戏规则中，共有两种方式凑成「一组牌」：

• 顺子：三张牌面数字连续的麻将，例如 [4,5,6]
• 刻子：三张牌面数字相同的麻将，例如 [10,10,10]

给定若干数字作为麻将牌的数值（记作一维数组 tiles），请返回所给 tiles 最多可组成的牌组数。

注意：凑成牌组时，每张牌仅能使用一次。

样例

输入：tiles = [2,2,2,3,4]
输出：1
解释：最多可以组合出 [2,2,2] 或者 [2,3,4] 其中一组牌。

输入：tiles = [2,2,2,3,4,1,3]
输出：2
解释：最多可以组合出 [1,2,3] 与 [2,3,4] 两组牌。

限制

• 1 <= tiles.length <= 10^5
• 1 <= tiles[i] <= 10^9

算法

(动态规划) $O(n \log n)$

1. 先将所有牌从小到大排序，并将其转换为一个频次数组，即 $nums(i) := (x, y)$ 表示从小到大第 $i$ 个数字为 $x$，且出现了 $y$ 次。
2. 设状态 $f(i, j, k)$ 表示为考虑了前 $i$ 种牌，其中第 $i$ 种牌有 $j$ 张作为顺子第一位的候补牌，且有 $k$ 张作为顺子第二位的候补牌时，凑出的最大牌组数。
3. 这里 $j$ 和 $k$ 的范围都是 $[0, 2]$，这是因为，如果有三张或以上的候补牌都凑成顺子当做牌组时，这些牌组完全可以拆开为小于三个的顺子（其余的都组成刻子）。例如，(1, 2, 3) 如果出现了 5 次，则完全可以拆为 (1, 1, 1), (2, 2, 2), (3, 3, 3) 外加两组 (1, 2, 3)。
4. 初始时，考虑第一种牌的数字的情况。第一种牌只可能作为顺子第一位的候补牌，即 $f(0, j, 0) = (y_0 - j) / 3$，拿出 $j$ 张牌作为顺子第一位，其余都组成刻子时的最大牌组数。其余待定。建立辅助数组，令 $g(i)$ 表示所有 $j$ 与 $k$ 情况下 $f(i, j, k)$ 的最大值。
5. 转移时，有两种情况：
   • 当前牌的数字完全不管前一种数字，这种情况和初始化的情况一样。转移 $f(i, j, 0) = g(i - 1) + (y_i - j) / 3$。
   • 当前牌的数字恰好比上一种牌的数字大 1，此时可以尝试转移顺子的情况，对于 $f(i, j, k)$，即拿出 $j$ 张牌放到顺子第一位，拿出 $k$ 张牌匹配顺子第二位。然后再枚举 $k0$，表示此次需要拿出 $k0$ 张牌与 $f(i - 1)$ 时的顺子第二位组成真正的顺子，剩余的牌都做刻子。
   • 转移 $f(i, j, k) = \max(f(i, j, k), f(i - 1, k, k0) + k0 + (y_i - j - k - k0) / 3$。此时需要保证 $j + k + k0 \le y_i$。
   • 最后更新 $g(i)$。
6. 最终答案为 $g(m - 1)$，其中 $m$ 为牌的数字种类数。

时间复杂度

• 排序构造 $nums$ 数组需要 $O(n \log n)$ 的时间。
• 动态规划的状态数为 $O(m)$，转移时间可以看做常数，故总时间复杂度为 $O(m)$。

空间复杂度

• 需要 $O(m)$ 的空间存储 $nums$ 数组和动态规划的状态。

C++ 代码

#define N 100010

class Solution {
private:
    int f[N][3][3], g[N];

public:
    int maxGroupNumber(vector<int>& tiles) {
        sort(tiles.begin(), tiles.end());
        const int n = tiles.size();
        vector<pair<int, int>> nums;

        int last = 0;
        for (int i = 1; i < n; i++) {
            if (tiles[i] != tiles[i - 1]) {
                nums.push_back(make_pair(tiles[i - 1], i - last));
                last = i;
            }
        }

        nums.push_back(make_pair(tiles[n - 1], n - last));

        // 动态规划

        const int m = nums.size();

        memset(f, 0x80, sizeof(f));
        memset(g, 0x80, sizeof(g));

        for (int j = 0; j <= 2; j++) {
            if (nums[0].second >= j)
                f[0][j][0] = (nums[0].second - j) / 3;

            g[0] = max(g[0], f[0][j][0]);
        }

        for (int i = 1; i < m; i++) {

            for (int j = 0; j <= 2; j++) {
                if (nums[i].second >= j)
                    f[i][j][0] = max(f[i][j][0], g[i - 1] + (nums[i].second - j) / 3);

                g[i] = max(g[i], f[i][j][0]);
            }

            if (nums[i].first == nums[i - 1].first + 1) { // 如果可以接上前一种牌作为顺子
                for (int j = 0; j <= 2; j++)
                    for (int k = 0; k <= 2; k++) {
                        for (int k0 = 0; k0 <= 2; k0++) {
                            if (nums[i].second < j + k + k0) continue;

                            f[i][j][k] = max(f[i][j][k],
                                f[i - 1][k][k0] + k0 + (nums[i].second - j - k - k0) / 3);
                        }

                        g[i] = max(g[i], f[i][j][k]);
                    }
            }
        }

        return g[m - 1];
    }
};