https://leetcode.cn/problems/candy/description/
贪心,策略是确定一侧的正确性,再确定另一侧的正确性,最后综合作为正确答案,其中先确定一侧的正确性是局部最优,确定两侧的正确性的局部最优,且找不到反例就可以推出全局最优答案
class Solution {
public int candy(int[] ratings) {
int[] num=new int[ratings.length];
Arrays.fill(num,1);
// 计算右边孩子大于左边孩子的情况
for(int i=1;i<ratings.length;i++)
if(ratings[i]>ratings[i-1])
num[i]=num[i-1]+1;
// 计算左边孩子大于右边孩子的情况
for(int i=ratings.length-2;i>=0;i--)
if(ratings[i]>ratings[i+1])
{
// 取左边和右边+1的最大值,作为本值
// 即只需要比相邻的最大值大1即可
// 即 : num[i]=Math.max(num[i-1],num[i+1]+1);
// 但是上面的循环已经计算过了,此时的num[i]一定比左边大,因此只需要让num[i]和num[i+1]+1比较即可
num[i]=Math.max(num[i],num[i+1] + 1);
}
int res=0;
for(int i=0;i<ratings.length;i++)res+=num[i];
return res;
}
}
标签:分发,ratings,int,左边,正确性,num,135,leetcode From: https://www.cnblogs.com/lxl-233/p/18383615