一、题目
给你一个下标从 0 开始的正整数数组 candiesCount ,其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries ,其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 。
你按照如下规则进行一场游戏:
你从第 0 天开始吃糖果。 你在吃完 所有 第 i - 1 类糖果之前,不能 吃任何一颗第 i 类糖果。 在吃完所有糖果之前,你必须每天 至少 吃 一颗 糖果。
请你构建一个布尔型数组 answer ,满足 answer.length == queries.length 。answer[i] 为 true 的条件是:在每天吃 不超过 dailyCapi 颗糖果的前提下,你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果;否则 answer[i] 为 false 。注意,只要满足上面 3 条规则中的第二条规则,你就可以在同一天吃不同类型的糖果。
请你返回得到的数组 answer 。
二、思路
根据规则,每天最多吃dailyCapi颗糖果,最少吃1颗,那么可以确定吃糖果数量的区间为:
使用一个sum数组,sum[i+1]代表candiesCount从0累加到i的和,由于吃糖果需要从最开始吃过来,那么需要吃糖果的区间为:
只需要两个区间相交,则能够吃到喜欢的糖果。
注:防止计算过程数据溢出,使用long型
三、代码
class Solution {
public boolean[] canEat(int[] candiesCount, int[][] queries) {
boolean[] ans = new boolean[queries.length];
long[] sum = new long[candiesCount.length + 1];
for (int i = 0; i < candiesCount.length; i++) {
sum[i+1] = sum[i] + candiesCount[i];
}
for (int i = 0; i < queries.length; i++) {
int[] query = queries[i];
long maxVal = (long)(query[1] + 1) * (long)query[2];
long minVal = (long)(query[1] + 1);
boolean eat = true;
if (minVal > sum[query[0]+1] || (maxVal < sum[query[0]] + 1)) {
eat = false;
}
ans[i] = eat;
}
return ans;
}
}
时间复杂度为O(candiesCount.length + queries.length),空间复杂度为O(candiesCount.length + queries.length)。