135. Candy Hard

1/**
2 * [135] Candy
3 *
4 * There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
5 * You are giving candies to these children subjected to the following requirements:
6 * 
7 * 	Each child must have at least one candy.
8 * 	Children with a higher rating get more candies than their neighbors.
9 * 
10 * Return the minimum number of candies you need to have to distribute the candies to the children.
11 *  
12 * Example 1:
13 * 
14 * Input: ratings = [1,0,2]
15 * Output: 5
16 * Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
17 * 
18 * Example 2:
19 * 
20 * Input: ratings = [1,2,2]
21 * Output: 4
22 * Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
23 * The third child gets 1 candy because it satisfies the above two conditions.
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	n == ratings.length
29 * 	1 <= n <= 2 * 10^4
30 * 	0 <= ratings[i] <= 2 * 10^4
31 * 
32 */
33pub struct Solution {}
34
35// problem: https://leetcode.com/problems/candy/
36// discuss: https://leetcode.com/problems/candy/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40impl Solution {
41    pub fn candy(ratings: Vec<i32>) -> i32 {
42        0
43    }
44}
45
46// submission codes end
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    #[test]
53    fn test_135() {
54    }
55}
56