原題鏈接
題目描述
一群孩子做游戲，現在請你根據游戲得分來發糖果，要求如下：
1. 每個孩子不管得分多少，起碼分到一個糖果，
2. 任意兩個相鄰的孩子之間，得分較多的孩子必須拿多一些糖果，(若相同則無此限制)
給定一個陣列arr代表得分陣列，請回傳最少需要多少糖果，
[要求]
時間復雜度為O(n), 空間復雜度為O(1)
示例
輸入：
[2, 4, 1, 5, 3]
輸出：
7
說明：
分配方案為：1，2，1，2，1
參考解法
/**
1、與前面的鄰居比較，前向遍歷分數陣列，
2、與后面的鄰居比較，后向遍歷分數陣列，
3、分別從兩邊遍歷選取較大值，計算結果
*/
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int a[] = { 2, 4, 1, 5, 3 };
System.out.println(candy(a));
}
public static int candy(int[] a) {
int n = a.length;
int l[] = new int[n];
int r[] = new int[n];
// 往陣列里填充特定值
Arrays.fill(l, 1);
Arrays.fill(r, 1);
for (int i = 1; i < l.length; i++) {
if (a[i] > a[i - 1])
l[i] = l[i - 1] + 1;
}
for (int i = r.length - 2; i >= 0; i--) {
if (a[i] > a[i + 1])
r[i] = r[i + 1] + 1;
}
int count = 0;
for (int i = 0; i < l.length; i++) {
count += Math.max(l[i], r[i]);
}
// for (int i = 0; i < l.length; i++) {
// System.out.printf("%d ", l[i]);
// }
// System.out.println();
// for (int i = 0; i < r.length; i++) {
// System.out.printf("%d ", r[i]);
// }
// System.out.println();
return count;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/140331.html
標籤：python
上一篇：C語言 桶排序
下一篇：c++小白如何寫出推箱子