problem
min heap
class Solution {
fun candy(ratings: IntArray): Int {
val size = ratings.size
if (size <= 1) return size
val candies = IntArray(size) { 1 }
val heap = PriorityQueue<Pair<Int,Int>>(compareBy { it.first })
for (i in 0 until size) {
heap.add(Pair(ratings[i], i))
}
while (heap.isNotEmpty()) {
val (rating, index) = heap.poll()
when (index) {
0 -> {
if (rating > ratings[index + 1]) candies[index] = candies[index + 1] + 1
}
size - 1 -> {
if (rating > ratings[index - 1]) candies[index] = candies[index - 1] + 1
}
else -> {
if (rating > ratings[index + 1]) candies[index] = candies[index + 1] + 1
if (rating > ratings[index - 1]) candies[index] = maxOf(candies[index], candies[index - 1] + 1)
}
}
}
return candies.sum()
}
}
greedy
class Solution {
fun candy(ratings: IntArray): Int {
val size = ratings.size
if (size <= 1) return size
val candies = IntArray(size) { 1 }
for (i in 1 until size) {
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1
}
for (i in size - 1 downTo(1)) {
if (ratings[i - 1] > ratings[i]) candies[i - 1] = maxOf(candies[i - 1], candies[i] + 1)
}
return candies.sum()
}
}