-
Notifications
You must be signed in to change notification settings - Fork 0
/
135.分发糖果.js
75 lines (72 loc) · 1.67 KB
/
135.分发糖果.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*
* @lc app=leetcode.cn id=135 lang=javascript
*
* [135] 分发糖果
*
* https://leetcode-cn.com/problems/candy/description/
*
* algorithms
* Hard (48.20%)
* Likes: 531
* Dislikes: 0
* Total Accepted: 72.4K
* Total Submissions: 150.6K
* Testcase Example: '[1,0,2]'
*
* 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。
*
* 你需要按照以下要求,帮助老师给这些孩子分发糖果:
*
*
* 每个孩子至少分配到 1 个糖果。
* 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
*
*
* 那么这样下来,老师至少需要准备多少颗糖果呢?
*
*
*
* 示例 1:
*
*
* 输入:[1,0,2]
* 输出:5
* 解释:你可以分别给这三个孩子分发 2、1、2 颗糖果。
*
*
* 示例 2:
*
*
* 输入:[1,2,2]
* 输出:4
* 解释:你可以分别给这三个孩子分发 1、2、1 颗糖果。
* 第三个孩子只得到 1 颗糖果,这已满足上述两个条件。
*
*/
// @lc code=start
/**
* @param {number[]} ratings
* @return {number}
*/
var candy = function(ratings) {
let ret = 1;
let inc = 1, dec = 0, pre = 1;
for (let i = 1; i < ratings.length; i++) {
if (ratings[i] >= ratings[i - 1]) {
if (ratings[i] === ratings[i - 1]) pre = 1;
else pre++;
ret += pre;
inc = pre;
dec = 0;
} else {
dec++;
if (dec === inc) {
dec++;
}
ret += dec;
pre = 1;
}
}
return ret;
};
// @lc code=end