LC.P1744[你能在你最喜欢的那天吃到你最喜欢的糖果吗？]
方法一：前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public boolean[] canEat(int[] candiesCount, int[][] queries) {
int n = candiesCount.length, m = queries.length;
boolean[] ans = new boolean[m];
long[] sum = new long[n + 1];
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + candiesCount[i - 1];
}
for (int i = 0; i < m; ++i) {
int type = queries[i][0], day = queries[i][1] + 1, cnt = queries[i][2];
long min = sum[type] / cnt + 1, max = sum[type + 1];
ans[i] = min <= day && day <= max;
}
return ans;
}
}
|
- 时间复杂度：$O(m + n)$
- 空间复杂度：$O(n)$
wechat
