leetcode: 135. Candy

kldaji·2022년 7월 4일
0

leetcode

목록 보기
40/56

problem

min heap

class Solution {
    fun candy(ratings: IntArray): Int {
        val size = ratings.size
        if (size <= 1) return size
        
        val candies = IntArray(size) { 1 }
        // sort by rating in ascending order
        val heap = PriorityQueue<Pair<Int,Int>>(compareBy { it.first }) // <rating, index>
        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 }
        // left to right
        // child who has higher rating than left neighbor child
        for (i in 1 until size) {
            if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1
        }
        // right to left
        // child who has higher rating than right neighbor child
        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()
    }
}
profile
다양한 관점에서 다양한 방법으로 문제 해결을 지향하는 안드로이드 개발자 입니다.

0개의 댓글