Medium

题目描述

给你一个下标从 0 开始的正整数数组 candiesCount，其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi]。

你按照如下规则进行一场游戏：

  • 你从第 0 天开始吃糖果。
  • 你在吃完 所有 第 i - 1 类糖果之前，不能 吃任何一颗第 i 类糖果。
  • 在吃完所有糖果之前，你必须每天 至少 吃 一颗 糖果。

请你构建一个布尔型数组 answer，满足 answer.length == queries.length 。answer[i] 为 true 的条件是：在不违反上述规则的情况下，你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果；否则 answer[i] 为 false。注意，只要满足上述规则，你可以在同一天吃不同类型的糖果。

请你返回得到的数组 answer。

示例 1：

输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
输出：[true,false,true]
解释：
1- 如果你在第 0 天吃 2 颗糖果(类型 0)，第 1 天吃 2 颗糖果(类型 0)，那么第 2 天你可以吃到类型 0 的糖果。
2- 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果(类型 0)，第 1 天吃 4 颗糖果(类型 0 和类型 1)，你也只能在第 2 天吃到类型 1 的糖果。换言之，你无法在第 2 天吃到类型 4 的糖果。
3- 如果你每天吃 1 颗糖果，你可以在第 13 天吃到类型 2 的糖果。

示例 2：

输入：candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
输出：[false,true,true,false,false]

提示：

  • 1 <= candiesCount.length <= 10^5
  • 1 <= candiesCount[i] <= 10^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 3
  • 0 <= favoriteTypei < candiesCount.length
  • 0 <= favoriteDayi <= 10^9
  • 1 <= dailyCapi <= 10^9

解题思路

这道题的关键是理解游戏规则并找到在指定日期能否吃到指定类型糖果的条件。

核心思路：

要在第 favoriteDay 天吃到第 favoriteType 类型的糖果，需要满足两个边界条件：

  1. 最早可能的日期：如果每天都吃上限 dailyCap 颗糖果，最早什么时候能吃到目标类型糖果？

    • 需要先吃完前面所有类型的糖果，设前面糖果总数为 prefixSum
    • 最早日期为 prefixSum / dailyCap（向下取整）

  2. 最晚可能的日期：如果每天只吃1颗糖果，最晚什么时候必须开始吃目标类型糖果？

    • 最晚日期为 prefixSum + candiesCount[favoriteType] - 1

只有当 favoriteDay 在这两个边界之间时，才可能在指定日期吃到目标糖果。

算法步骤：

  1. 计算前缀和数组，方便快速获取前 i 类糖果的总数
  2. 对每个查询，计算最早和最晚可能的日期
  3. 判断 favoriteDay 是否在合理范围内

时间复杂度： O(n + q)，其中 n 是糖果类型数量，q 是查询数量 空间复杂度： O(n)，存储前缀和数组

代码实现

class Solution {
public:
    vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
        int n = candiesCount.size();
        vector<long long> prefixSum(n + 1, 0);
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
        }
        
        vector<bool> result;
        for (auto& query : queries) {
            int favoriteType = query[0];
            long long favoriteDay = query[1];
            long long dailyCap = query[2];
            
            // 最早可能的日期：前面的糖果总数 / 每天最大吃糖数
            long long earliestDay = prefixSum[favoriteType] / dailyCap;
            
            // 最晚可能的日期：前面糖果总数 + 当前类型糖果数 - 1
            long long latestDay = prefixSum[favoriteType + 1] - 1;
            
            // 判断目标日期是否在合理范围内
            result.push_back(favoriteDay >= earliestDay && favoriteDay <= latestDay);
        }
        
        return result;
    }
};

class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(candiesCount)
        prefix_sum = [0] * (n + 1)
        
        # 计算前缀和
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + candiesCount[i]
        
        result = []
        for favorite_type, favorite_day, daily_cap in queries:
            # 最早可能的日期：前面的糖果总数 // 每天最大吃糖数
            earliest_day = prefix_sum[favorite_type] // daily_cap
            
            # 最晚可能的日期：前面糖果总数 + 当前类型糖果数 - 1
            latest_day = prefix_sum[favorite_type + 1] - 1
            
            # 判断目标日期是否在合理范围内
            result.append(earliest_day <= favorite_day <= latest_day)
        
        return result

public class Solution {
    public bool[] CanEat(int[] candiesCount, int[][] queries) {
        int n = candiesCount.Length;
        long[] prefixSum = new long[n + 1];
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
        }
        
        bool[] result = new bool[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int favoriteType = queries[i][0];
            long favoriteDay = queries[i][1];
            long dailyCap = queries[i][2];
            
            // 最早可能的日期：前面的糖果总数 / 每天最大吃糖数
            long earliestDay = prefixSum[favoriteType] / dailyCap;
            
            // 最晚可能的日期：前面糖果总数 + 当前类型糖果数 - 1
            long latestDay = prefixSum[favoriteType + 1] - 1;
            
            // 判断目标日期是否在合理范围内
            result[i] = favoriteDay >= earliestDay && favoriteDay <= latestDay;
        }
        
        return result;
    }
}

var canEat = function(candiesCount, queries) {
    const n = candiesCount.length;
    const prefixSum = new Array(n + 1).fill(0);
    
    // 计算前缀和
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
    }
    
    const result = [];
    for (const [favoriteType, favoriteDay, dailyCap] of queries) {
        // 最早可能的日期：前面的糖果总数 / 每天最大吃糖数
        const earliestDay = Math.floor(prefixSum[favoriteType] / dailyCap);
        
        // 最晚可能的日期：前面糖果总数 + 当前类型糖果数 - 1
        const latestDay = prefixSum[favoriteType + 1] - 1;
        
        // 判断目标日期是否在合理范围内
        result.push(favoriteDay >= earliestDay && favoriteDay <= latestDay);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n + q)，其中 n 是糖果类型数量，q 是查询数量。需要 O(n) 时间计算前缀和，O(q) 时间处理所有查询
空间复杂度O(n)，存储前缀和数组