There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
本题有一点需要注意的是,题目只要求相邻小朋友rating大的,candies分得多。
对于相邻的小朋友ratings相同可以分得个数不一样的糖果。
也就是 1 2 3 3 3 3 4 5 糖果数
对应为1 2 3 1 1 1 2 3是合理的。中间的两个3 3 随便取值,但是min的话肯定是取1啦
定义c[i]表示小朋友i可以分得的最少糖果数
因为上述ratings相等的情况合理,那么可以不考虑ratings相等的情况,
可以把这个数组其他部分分成若干严格单调区间[升,降随意组合],观察可知:
1 对于上拐点 c[i] =max(升区间长度,降区间长度);
2 对于下拐点c[i]肯定等于1 然后随着区间,逐渐递增;
然后我就陷入了找升降区间的思路中不可自拔-。-
然后看了大牛们代码发现,可以分两遍扫;
1. 第一遍扫严格单调增区间,c[i] = c[i-1]+1;
2. 第二遍扫严格单调减区间, Math.max(c[i],c[i+1]+1);其中c[i]是第一遍扫单增区间的赋值,
c[i+1]+1是本次扫单减区间的赋值;似乎只用考虑上拐点就可以了,
但是拐点的判断有点麻烦,所以每个都考虑下好了-。-
同时在第二遍扫的过程中就可以把min求出来。
代码:
public int candy(int[] ratings) { // Note: The Solution object is instantiated only once and is reused by each test case. if(ratings == null||ratings.length == 0) return 0; int len = ratings.length; int c[] = new int[len]; Arrays.fill(c,1); for(int i = 1;i<=len-1;i++){ if(ratings[i]>ratings[i-1])//单增区间 c[i] = c[i-1]+1; } //c[len-1]的值不会改变了,因为len-1是: //1. 单增区间的尾部,后面没有值了,不是上拐点 //2. 单减区间的尾部,肯定是初始值1 //3. 某一重复值,取初始值1 int min = c[len-1]; for(int i = len-2;i>=0;i--){//单减区间 if(ratings[i+1]<ratings[i]){ c[i] = Math.max(c[i],c[i+1]+1); } min = min+c[i]; } return min; }
ps 这种两种单调的情况可以扫两遍啊亲,我记得买卖股票那题也似这种方式扫两遍啊,
不长记性!!我回去在把那题做一遍。。
相关推荐
我自己在新学erlang,在LeetCode OJ上找了题目练习,题目很适合新手熟悉语言,但是LeetCode OJ里面只有几门主流语言的答案,下面是已完成的erlang源代码,后续有空再做其他问题续传,题目包含:(源码开头都有题目...
Candy_leetcode:刷leetcode的代码汇总
LeetCode.135分发糖果135. 分发糖果解题思路:3、最后发放糖果时必须同时满足左规则、右规则,所以取左右规则最大值public int candy
leetcode中国 leetcode-chinese-crawler 此代码用于USTC 2019秋季学期web课程开放实验 概述 爬取 LeetCode中文试题。 运行环境 Windows 10 python 3; 库: requests requests_toolbelt codecs json time random json...
leetcode 和 oj #问题列表(按标题升序) 标题|添加日期|AC 利率 ---|---|---|--- 3Sum |2012-01-17|16.4% 3Sum Closest|2012-01-18|26.8% 4Sum|2012-01-26 |21.3% 二进制加法|2012-04-02|25.6% 两个数相加|2011-11-...
candy: minimum_depth_binary_tree: twoSum: regularExpressionMathcing: sameTree: find_content_children: LeetCode 算法题 时间复杂度和空间复杂度权衡,时间复杂度的提升是以空间复杂度为代价的 仔细观察,...
leetcode最大蓄水量 记录数据结构和leetCode算法题 数据结构 sparsearray 稀疏数组 singlequeue 数组模拟队列 circelqueue 数组模拟环形队列 singlequeue 单向链表 doublelink 双向链表 circlesinglelink 环形链表 ...
candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
leetcode_easy_python 挑战1431:给定数组糖果和整数extraCandies,其中candy [i]代表第i个孩子拥有的糖果数量。 对于每个孩子,检查是否有一种方法可以在孩子之间分配额外的糖果,以便他或她可以在其中拥有最多的...
leetcode 力码 【吾生也有涯,而知也无涯。】 刷题解题记录: 大批: 220 包含重复 III 考 55 跳跃游戏45 跳跃游戏 II121 买卖股票的最佳时机 122 买卖股票的最佳时机 II123 买卖股票的最佳时机 III188 买卖股票的...
leetcode打不开玩具问题 编码练习 string input; while (getline(cin, input)) { cout << "input: " << input << endl; string output = candyCrush(input); cout << "output: " << ...
网上搜集的华为面试机试题库#字符串分割#服务器广播# #分子弹,这个题想了好久,最后发现是leetcode上面的candy那一类的#无重复字符的最长字串
谷歌师兄的leetcode刷题笔记 甜蜜银行 :candy: Sweet Bank 是Kotlin中的一个 Android 应用程序,我开发它是为了尝试移动开发的一些原则,例如范围分离、设计模式(例如 MVVM)等等。 我使用 Starling Bank API 来...
3. iterate two candy arrays, sum the max element from two arrays. 4. 只关注增量,如果rat
(C语言是我初恋:candy: ) 目前有的: Java 操作系统 计网 JVM leetcode 计算机基础 Android 设计模式 数据库 工具 面筋 :laptop: :cloud: :ogre: :lion: :globe_showing_Asia-Australia: :robot: :deer: :memo:...
AlgoHub囊括了 POJ, ZOJ, leetcode, HackerRank 等网站的经典题目(一些质量不高的题目则忽略),且 AlgoHub有非常简单的加题系统,用户不需要写一行代码即可自己添加题目,所以AlgoHub的题库还在飞速增长中。...