代码随想录day29 || 134 加油站，135 分糖果，860 柠檬水找零，406 根据身高重建队列

加油站

func canCompleteCircuit(gas []int, cost []int) int {
	// 思路，首先统计一个差值数组，表示行驶到下一个加油站可以补充的油量，然后加总差值数组，
	// 如果小于0，表示从起始位置到目前为止剩余油量小于0，不足以跑完全程，同时将起始位置放到遍历的下一个位置

	if len(gas) == 0 || len(cost) == 0 {
		return 0
	}

	// 如果跑完全程所消耗油量小于提供油量，那么无法跑完
	var total int
	for i := 0; i < len(gas); i++ {
		total += gas[i] - cost[i]
	}
	if total < 0 {
		return -1
	}

	var start, cursum int
	for i:=0; i<len(gas); i++ {
		cursum += gas[i] - cost[i]
		if cursum < 0 {
			start = i+1
			cursum = 0
		}
	}
	return start
}

135 分糖果

func candy(ratings []int) int {
	// 思路，对比分数需要考虑和左右两边对比的情况，所以优先考虑一侧，然后再计算另一个，两边取最值即可
	if len(ratings) == 1 {
		return 1
	}


	var length = len(ratings)
	var left, right = make([]int, length), make([]int, length)
	left[0] = 1
	right[length - 1] = 1
	for i:=1; i<length; i++ {
		if ratings[i] > ratings[i-1] {
			left[i] = left[i-1] + 1 // 如果评分高于左边，那么给予数量多一个
		}else {
			left[i] = 1
		}
	}

	// 为什么这里要倒序遍历呢？因为如果还是正序，那么就和上面的遍历过程一致了，我们的初始位置一定是最后一位，这样才能再基础上对比加数量
	for i:=length-2; i >= 0; i--{
		if ratings[i] > ratings[i+1] {
			right[i] = right[i+1] + 1
		}else {
			right[i] = 1
		}
	}

	var res int
	//fmt.Println(left, right)
	for i:=0; i<length; i++{
		if right[i] > left[i] {
			res += right[i]
		}else {
			res += left[i]
		}
	}
	return res
}

135 柠檬水找零

func lemonadeChange(bills []int) bool {
	// 思考一下，遍历数组，如果5，跳过，如果10，检查map是否有5，如果20，优先检查10，然后检查5
	var exchange = make(map[int]int) // bill; count

	for _, v := range bills {
		switch v {
		case 5:
			exchange[5]++
		case 10:
			// 检查是否有5的零钱
			if exchange[5] == 0 {
				return false
			}

			exchange[5]--
			exchange[10]++
		case 20:// 20 不必存入map，因为根本没有找零作用
			// 优先匹配10+5 次要匹配5+5+5
			if exchange[5] > 0 && exchange[10] > 0 ||
				exchange[5] >= 3 {
				if exchange[10] > 0 {
					exchange[10]--
					exchange[5]--
				}else {
					exchange[5] -= 3
				}
			}else {
				return false
			}
		}

	}
	return true
}

135 根据身高重建队列

func reconstructQueue(people [][]int) [][]int {
	sort.Slice(people, func(i, j int) bool {
		if people[i][0] == people[j][0] {
			return people[i][1] < people[j][1]  // 位次升序
		}
		return people[i][0] > people[j][0] // 身高降序
	})
	fmt.Println(people)

	
	var res [][]int
	for _, v := range people {
		idx := v[1]
		res = append(res[0 : idx], append([][]int{v}, res[idx : ]...)...)
	}

	return res
}