如何高效解决 LeetCode 135. Candy 分发糖果难题？

本文共计941个文字，预计阅读时间需要4分钟。

通过两次遍历，分配的糖果就可以满足题目要求。这里的贪心策略即在每次遍历中，只考虑并更新相邻元素的大小关系。

一、题目大意标签：贪心链接：https://leetcode.cn/problems/candy/

二、代码示例（Python）

pythondef candy(nums): n=len(nums) if n <=1: return n

# 初始化糖果数组，每个学生至少获得一个糖果 candy=[1] * n

# 第一次遍历：从左到右，如果当前学生成绩高于左侧学生，则给其更多的糖果 for i in range(1, n): if nums[i] > nums[i - 1]: candy[i]=candy[i - 1] + 1

# 第二次遍历：从右到左，如果当前学生成绩高于右侧学生，则给其更多的糖果 for i in range(n - 2, -1, -1): if nums[i] > nums[i + 1]: candy[i]=max(candy[i], candy[i + 1] + 1)

# 计算总共需要的糖果数 return sum(candy)

通过两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。 一、题目大意

标签: 贪心

leetcode.cn/problems/candy

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。