小扣当前位于魔塔游戏第一层，共有 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题目，使用堆进行遍历
