题目

小扣当前位于魔塔游戏第一层，共有 N 个房间，编号为 0 ~ N-1。

每个房间的补血道具/怪物对于血量影响记于数组 nums，其中正数表示道具补血数值，即血量增加对应数值；

负数表示怪物造成伤害值，即血量减少对应数值；0 表示房间对血量无影响。

小扣初始血量为 1，且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪，为保证血量始终为正值，

小扣需对房间访问顺序进行调整，每次仅能将一个怪物房间（负数的房间）调整至访问顺序末尾。

请返回小扣最少需要调整几次，才能顺利访问所有房间。若调整顺序也 *** 完全部房间，请返回 -1。

示例 1：输入：nums = [100,100,100,-250,-60,-140,-50,-50,100,150] 输出：1

解释：初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。

示例 2：输入：nums = [-200,-300,400,0]输出：-1

解释：调整访问顺序也无法完成全部房间的访问。

提示：1 <= nums.length <= 10^5

-10^5 <= nums[i] <= 10^5

解题思路分析

1、堆；时间复杂度O(nlog(n))，空间复杂度O(n)

func magicTower(nums []int) int { intHeap := make(IntHeap, 0) heap.Init(&intHeap) blood := 0 sum := 0 res := 0 for i := 0; i < len(nums); i++ { sum = sum + nums[i] if nums[i] < 0 { heap.Push(&intHeap, nums[i]) if blood+nums[i] < 0 { res++ minValue := heap.Pop(&intHeap).(int) blood = blood - minValue } } blood = blood + nums[i] } if sum < 0 { return -1 } return res } type IntHeap []int func (h IntHeap) Len() int { return len(h) } // 小根堆<,大根堆变换方向> func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) } func (h *IntHeap) Pop() interface{} { value := (*h)[len(*h)-1] *h = (*h)[:len(*h)-1] return value }

2、堆；时间复杂度O(nlog(n))，空间复杂度O(n)

func magicTower(nums []int) int { sum := 0 for i := 0; i < len(nums); i++ { sum = sum + nums[i] } if sum < 0 { return -1 } intHeap := make(IntHeap, 0) heap.Init(&intHeap) blood := 0 res := 0 for i := 0; i < len(nums); i++ { heap.Push(&intHeap, nums[i]) blood = blood + nums[i] if blood < 0 { minValue := heap.Pop(&intHeap).(int) blood = blood - minValue res++ } } return res } type IntHeap []int func (h IntHeap) Len() int { return len(h) } // 小根堆<,大根堆变换方向> func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) } func (h *IntHeap) Pop() interface{} { value := (*h)[len(*h)-1] *h = (*h)[:len(*h)-1] return value }

总结

Medium题目，使用堆进行遍历