/**
* 解法:贪心
* 思路:
* 要想分出最少的糖果,利用贪心思想,肯定是相邻位置没有增加的情况下大家都分到1,
* 相邻位置有增加的情况下,分到糖果数加1就好。什么情况下会增加糖果,相邻位置有得
* 分差异,可能是递增可能是递减,如果是递增的话,糖果依次加1,如果是递减糖果依次减1?
* 这不符合最小,必须从1开始加才是最小,那我们可以反向加1.
* 时间复杂度:O(n),单独遍历两次.
* 空间复杂度:O(n)。记录每个位置糖果数的辅助数组.
*/
export function candy(arr: number[]): number {
const len = arr.length
if (len <= 1) return len
let nums: number[] = []
for (let i = 0; i < len; i++) {
nums[i] = 1
}
for (let i = 1; i < len; i++) {
if (arr[i] > arr[i - 1]) { // 如果右边在递增,每次增加一个
nums[i] = nums[i - 1] + 1
}
}
let res = nums[len - 1] // 记录总糖果数
for (let i = len - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1] && nums[i] <= nums[i + 1]) { // 如果左边更大但是糖果树更小
nums[i] = nums[i + 1] + 1
}
res += nums[i] // 累加和
}
return res
}
一站式解决前端面试高频算法题