魔塔游戏百度百科，catcap魔塔攻略
目前，标题按钮位于魔法塔游戏的一楼，一共有N个房间，编号从0到N-1。每个房间的补血道具/怪物对血量的影响记录在数组num中，其中正数代表道具的补血值，即血量增加对应的值，负数代表补血值。代表。数值为怪物造成的伤害值，即相当于血量减少的值，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) 血液：=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)血液=血液- minValue } } 血液=血液+ nums[i] } if sum 0 { return -1 } return res}type IntHeap []intfunc (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 接口{}) { *h=追加(*h, x.(int))}func (h *IntHeap ) pop()接口{} { value :=(*h)[len(*h)-1] *h=(*h)[:len(*h)-1]返回值} 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) 血液：=0 res :=0 for i :=0; i len(nums); i++ { heap.Push(intHeap, nums[i]) 血液=血液+ nums[i ] if Blood 0 { minValue :=heap.Pop(intHeap).(int) Blood=Blood - minValue res++ } } return res}type IntHeap []intfunc (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 接口{}) { *h=附加(*h, x.(int))}func (h * IntHeap ) Pop() interface {} { value :=(*h)[len(*h)-1] *h=(*h)[:len(*h)-1] return value} Medium 问题及使用总结它。堆遍历
