LeetCode135☞分糖果

关联LeetCode题号135

本题特点

• 贪心
• 两次遍历，一次正序遍历，只比较左边，左边比右边大的情况 i-1 i
• 一次倒序遍历，只比较右边的，右边比左边大 i+1 i

本题思路

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candy = [1] * len(ratings)
        # 右大于左
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                candy[i] = candy[i-1] + 1
        # 左大于右
        for j in range(len(ratings)-2, -1, -1):
            if ratings[j] > ratings[j+1]:
                candy[j] = max(candy[j+1]+1, candy[j])
        print(candy)
        return sum(candy)

package leetcode;

import org.junit.jupiter.api.Test;

/**
 * File Description: Candy
 * Author: Your Name
 * Date: 2024/12/24
 */
public class Candy_135 {
    public int candy(int[] ratings) {
        int[] candy = new int[ratings.length];
        candy[0] = 1;
        for (int i=1; i<ratings.length; i++){
//            if (ratings[i-1] < ratings[i]){
//                candy[i] = candy[i-1] + 1;
//            }else{
//                candy[i] = 1;
//            }
            candy[i] = (ratings[i-1] < ratings[i]) ? candy[i-1]+1 : 1;
        }
        for(int j=ratings.length-2; j>=0; j--){
            if (ratings[j] > ratings[j+1]){
                candy[j] = Math.max(candy[j], candy[j+1]+1);
            }

        }
        int sum = 0;
        for(int c: candy){
            sum += c;
        }
        return sum;
    }

    @Test
    public void TestCandy(){
        int[] rating = {1,0,2};
        System.out.println(candy(rating));
    }
}