趣味SQL: 力扣135. 分发糖果

newkid

原题链接

135. 分发糖果
困难
相关标签
相关企业
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。



示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。



提示：

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings <= 2 * 104
  
  

newkid

create table candy (id number, rating number);

delete candy;

insert into candy
select level
      ,regexp_substr(s,'[^,]+',1,level)
from (select '1,3,2,2,2,1,3,4,4,4,4,6,6,6,5,4,3,3,3,7,8,9,9,9,3,2,5,5,5' s from dual
      )
connect by level<=regexp_count(s,',')+1;

〇〇

相邻两个孩子评分更高的孩子会获得更多的糖果->相邻两个孩子评分一样高，某个孩子可以获得更多的糖果

newkid

〇〇 发表于 2024-9-10 08:29
相邻两个孩子评分更高的孩子会获得更多的糖果->相邻两个孩子评分一样高，某个孩子可以获得更多的糖果

这规则就是这样，分数一样的孩子得到的糖果数可以相同也可以不同。目标是总糖果数最少

〇〇

1.先给全部的人一块，然后删除**的，
2.重复1，没有人了停止

〇〇

〇〇 发表于 2024-9-12 13:17
1.先给全部的人一块，然后删除**的，2.重复1，没有人了停止

如果数字连续，每人糖块和原始分数一样
with recursive t(id,rt,candy)
as(select id,rating-min(rating)over(),1,from candy
union all
select id,rt-min(rt)over(),candy+1 from t where rt>0
)
select id,max(candy) from t group by id order by id;

newkid

你的SQL在ORACLE上跑我的测试数据：

        ID MAX(CANDY)
---------- ----------
         1          1
         2          3
         3          2
         4          2
         5          2
         6          1
         7          3
         8          4
         9          4
        10          4
        11          4
        12          6
        13          6
        14          6
        15          5
        16          4
        17          3
        18          3
        19          3
        20          7
        21          8
        22          9
        23          9
        24          9
        25          3
        26          2
        27          5
        28          5
        29          5

29 rows selected.

对比一下这个结果，显然你的糖果发多了：
       ID     RATING CANDY_COUNT
--------- ---------- -----------
        1          1           1
        2          3           2
        3          2           1
        4          2           1
        5          2           2
        6          1           1
        7          3           2
        8          4           3
        9          4           1
       10          4           1
       11          4           1
       12          6           2
       13          6           1
       14          6           4
       15          5           3
       16          4           2
       17          3           1
       18          3           1
       19          3           1
       20          7           2
       21          8           3
       22          9           4
       23          9           1
       24          9           3
       25          3           2
       26          2           1
       27          5           2
       28          5           1
       29          5           1

29 rows selected.

〇〇

因为我没想到怎么处理同分异果

newkid

分析：当一个孩子分数比相邻孩子高，不管高多少，只需多给一颗糖即可满足需求。如果一个孩子左右都没有更高的分数，则这个孩子只需发一颗糖。把这样的孩子作为起点，左右分别找连续上升的分数，找到一个增加一颗糖。
所以题目任务变成：
寻找连续上升或者连续下降的段，这种线段的低点只需发一颗糖，其他人的糖果数就是他和**点的相差人数加1。
当一个孩子处于高峰点，即同时比左边和右边的都更高，则计算他和左右**点的距离，取其最大值。
在平直的段中，除了两边的端点，所有孩子都发只需一颗糖。两边端点可能是其他上升下降段的高点，此时按上面的计算方法发糖。

select id,max(rating) as rating,max(candy_cnt) as candy_count --------- 起终点在结果中都会出现两次，属于两个不同的段，取其最大值
  from candy
     match_recognize (
     order by id
     measures
        match_number() as grp
       ,CLASSIFIER() AS var_match
       ,count(*) as rn
       ,final count(*) as cnt
       ,case
        WHEN CLASSIFIER()='END_POINT' and rating>prev(rating)  --------- 上升段
             or CLASSIFIER()='UP' then count(*)
        when CLASSIFIER()='END_POINT' and rating<prev(rating)  --------- 下降段
             or CLASSIFIER()='DOWN' then final count(*) - RUNNING count(*)+1
        ELSE 1  ------- 平直段
        end as candy_cnt
     all rows per match
     after match skip to last end_point --------- 每一段的终点都是下一段的起点
     pattern( up+ end_point | flat+ end_point | down+ end_point)
     define up as rating<next(rating)
           ,flat as rating=next(rating)
           ,down as rating>next(rating)
     )
group by id  --------- 起终点在结果中都会出现两次，属于两个不同的段
order by id;


       ID     RATING CANDY_COUNT
--------- ---------- -----------
        1          1           1
        2          3           2
        3          2           1
        4          2           1
        5          2           2
        6          1           1
        7          3           2
        8          4           3
        9          4           1
       10          4           1
       11          4           1
       12          6           2
       13          6           1
       14          6           4
       15          5           3
       16          4           2
       17          3           1
       18          3           1
       19          3           1
       20          7           2
       21          8           3
       22          9           4
       23          9           1
       24          9           3
       25          3           2
       26          2           1
       27          5           2
       28          5           1
       29          5           1

29 rows selected.