目录
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 (SELECTkid_id,rating,ROW_NUMBER() OVER (ORDER BY kid_id) AS seq_numFROMkids_rating
)
SELECTkid_id,rating,seq_num
FROMRankedKids;| kid_id | rating | seq_num |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 0 | 2 |
| 3 | 2 | 3 |
第二步：结合左右遍历情况计算糖果数
-- 结合从左到右和从右到左遍历情况，一次性计算糖果数，展示中间结果
WITH RankedKids AS (SELECTkid_id,rating,ROW_NUMBER() OVER (ORDER BY kid_id) AS seq_numFROMkids_rating
),
CandyDistribution AS (SELECTrk.kid_id,rk.rating,MAX(CASEWHEN 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) + 1WHEN 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) + 1ELSE 1END) AS candyFROM (SELECTkid_id,rating,seq_num,1 AS candyFROMRankedKids) rkGROUP BYrk.kid_id,rk.rating,rk.seq_num
)
SELECTkid_id,rating,candy
FROMCandyDistribution;| kid_id | rating | candy |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 0 | 1 |
| 3 | 2 | 2 |
这里在 CandyDistribution CTE 中，通过在 MAX 函数里嵌套 CASE WHEN 语句，把从左到右（使用 LAG 函数判断左边孩子情况）和从右到左（使用 LEAD 函数判断右边孩子情况）的糖果数更新逻辑合并在一起了。对于每个孩子，取满足条件的糖果数中的最大值（因为要同时满足左右两边比较的规则），初始时每个孩子糖果数设为 1。这样就简化了之前分两次更新糖果数的操作，一次计算就得出相对合理的每个孩子的糖果数情况。
第三步：统计最少需要的糖果总数（最终结果）
-- 统计最少需要的糖果总数，最终结果
WITH RankedKids AS (SELECTkid_id,rating,ROW_NUMBER() OVER (ORDER BY kid_id) AS seq_numFROMkids_rating
),
CandyDistribution AS (SELECTrk.kid_id,rk.rating,MAX(CASEWHEN 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) + 1WHEN 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) + 1ELSE 1END) AS candyFROM (SELECTkid_id,rating,seq_num,1 AS candyFROMRankedKids) rkGROUP BYrk.kid_id,rk.rating,rk.seq_num
)
SELECTSUM(candy) AS total_candy
FROMCandyDistribution;| total_candy |
|---|
| 5 |
3 小结
文章利用SQL模拟常规的双遍历更新逻辑完整地解决了 “分发糖果” 问题，整体思路依然是先从左到右遍历更新一次糖果数，再从右到左遍历更新一次糖果数，最后统计糖果总数，只不过借助窗口聚合函数来更方便地实现相关逻辑。
如果您觉得本文还不错，对你有帮助，那么不妨可以关注一下我的数字化建设实践之路专栏，这里的内容会更精彩。
专栏 原价99，现在活动价59.9，按照阶梯式增长，还差5个人上升到69.9，最终恢复到原价。
专栏优势：
（1）一次收费持续更新。
（2）实战中总结的SQL技巧，帮助SQLBOY 在SQL语言上有质的飞越，无论你应对业务难题及面试都会游刃有余【全网唯一讲SQL实战技巧，方法独特】
SQL很简单，可你却写不好？每天一点点，收获不止一点点-CSDN博客
（3）实战中数仓建模技巧总结，让你认识不一样的数仓。【数据建模+业务建模，不一样的认知体系】（如果只懂数据建模而不懂业务建模，数仓体系认知是不全面的）
（4）数字化建设当中遇到难题解决思路及问题思考。
我的专栏具体链接如下
数字化建设通关指南_莫叫石榴姐的博客-CSDN博客