当前位置：首页 > article >正文

SQL进阶技巧:如何计算算法题分发糖果问题？

article 2024/12/21 14:56:41

0 问题描述

1 数据准备

2 问题分析

3 小结

专栏优势：（1）一次收费持续更新。

0 问题描述

有 n 个孩子站成一排，每个孩子都有一个评分值（整数），你需要按照以下要求给这些孩子分发糖果：

每个孩子至少分配到 1 颗糖果。
评分更高的孩子必须比他左右两边评分低的孩子获得更多的糖果（如果有的话）。
求最少需要多少颗糖果来满足上述条件。

例如，给定孩子的评分数组为 [1, 0, 2]，那么最少需要的糖果数是 5（分别给这三个孩子分配 2、1、2 颗糖果）。

1 数据准备

-- 创建 kids_rating 表
CREATE TABLE kids_rating (
    kid_id INT,
    rating INT
);

-- 插入示例数据
INSERT INTO kids_rating VALUES
(1, 1),
(2, 0),
(3, 2);

2 问题分析

可以通过两次遍历数组（在 SQL 中模拟这个过程）来解决这个问题。

第一次遍历（从左到右）：

初始化每个孩子的糖果数为 1。
从左到右遍历，如果当前孩子的评分大于左边孩子的评分，那么当前孩子的糖果数应该比左边孩子多 1（满足评分高的孩子糖果更多的条件）。

第二次遍历（从右到左）：

再次检查每个孩子的糖果数，从右到左遍历，如果当前孩子的评分大于右边孩子的评分，并且当前孩子的糖果数小于等于右边孩子的糖果数（说明之前从左到右分配时可能没满足条件），那么需要更新当前孩子的糖果数为右边孩子的糖果数加 1。

最后统计糖果总数：

对所有孩子最终分配的糖果数进行求和，得到最少需要的糖果总数。

第一步：添加序号列并展示（模拟从左到右顺序，类似数组索引）

-- 使用窗口函数添加序号列，方便后续按顺序处理数据，展示中间结果
WITH RankedKids AS (
    SELECT
        kid_id,
        rating,
        ROW_NUMBER() OVER (ORDER BY kid_id) AS seq_num
    FROM
        kids_rating
)
SELECT
    kid_id,
    rating,
    seq_num
FROM
    RankedKids;

kid_id	rating	seq_num
1	1	1
2	0	2
3	2	3

第二步：结合左右遍历情况计算糖果数

-- 结合从左到右和从右到左遍历情况，一次性计算糖果数，展示中间结果
WITH RankedKids AS (
    SELECT
        kid_id,
        rating,
        ROW_NUMBER() OVER (ORDER BY kid_id) AS seq_num
    FROM
        kids_rating
),
CandyDistribution AS (
    SELECT
        rk.kid_id,
        rk.rating,
        MAX(
            CASE
                WHEN rk.rating > LAG(rk.rating, 1, rk.rating) OVER (ORDER BY rk.seq_num) THEN LAG(candy, 1, 1) OVER (ORDER BY rk.seq_num) + 1
                WHEN rk.rating > LEAD(rk.rating, 1, rk.rating) OVER (ORDER BY rk.seq_num DESC) THEN LEAD(candy, 1, 1) OVER (ORDER BY rk.seq_num DESC) + 1
                ELSE 1
            END
        ) AS candy
    FROM (
        SELECT
            kid_id,
            rating,
            seq_num,
            1 AS candy
        FROM
            RankedKids
    ) rk
    GROUP BY
        rk.kid_id,
        rk.rating,
        rk.seq_num
)
SELECT
    kid_id,
    rating,
    candy
FROM
    CandyDistribution;

kid_id	rating	candy
1	1	2
2	0	1
3	2	2

这里在 CandyDistribution CTE 中，通过在 MAX 函数里嵌套 CASE WHEN 语句，把从左到右（使用 LAG 函数判断左边孩子情况）和从右到左（使用 LEAD 函数判断右边孩子情况）的糖果数更新逻辑合并在一起了。对于每个孩子，取满足条件的糖果数中的最大值（因为要同时满足左右两边比较的规则），初始时每个孩子糖果数设为 1。这样就简化了之前分两次更新糖果数的操作，一次计算就得出相对合理的每个孩子的糖果数情况。

第三步：统计最少需要的糖果总数（最终结果）

-- 统计最少需要的糖果总数，最终结果
WITH RankedKids AS (
    SELECT
        kid_id,
        rating,
        ROW_NUMBER() OVER (ORDER BY kid_id) AS seq_num
    FROM
        kids_rating
),
CandyDistribution AS (
    SELECT
        rk.kid_id,
        rk.rating,
        MAX(
            CASE
                WHEN rk.rating > LAG(rk.rating, 1, rk.rating) OVER (ORDER BY rk.seq_num) THEN LAG(candy, 1, 1) OVER (ORDER BY rk.seq_num) + 1
                WHEN rk.rating > LEAD(rk.rating, 1, rk.rating) OVER (ORDER BY rk.seq_num DESC) THEN LEAD(candy, 1, 1) OVER (ORDER BY rk.seq_num DESC) + 1
                ELSE 1
            END
        ) AS candy
    FROM (
        SELECT
            kid_id,
            rating,
            seq_num,
            1 AS candy
        FROM
            RankedKids
    ) rk
    GROUP BY
        rk.kid_id,
        rk.rating,
        rk.seq_num
)
SELECT
    SUM(candy) AS total_candy
FROM
    CandyDistribution;