题目描述
小扣当前位于魔塔游戏第一层，共有 N 个房间，编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums，其中正数表示道具补血数值，即血量增加对应数值；负数表示怪物造成伤害值，即血量减少对应数值；0 表示房间对血量无影响。 小扣初始血量为 1，且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪，为保证血量始终为正值，小扣需对房间访问顺序进行调整，每次仅能将一个怪物房间（负数的房间）调整至访问顺序末尾。请返回小扣最少需要调整几次，才能顺利访问所有房间。若调整顺序也无法访问完全部房间，请返回 -1。
Example 1:
输入：nums = [100,100,100,-250,-60,-140,-50,-50,100,150] 输出：1 解释：初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。
Example 2:
输入：nums = [-200,-300,400,0] 输出：-1 解释：调整访问顺序也无法完成全部房间的访问。
Constraints:
- 1 <= nums.length <= 10^5
- -10^5 <= nums[i] <= 10^5
解题思路
- 使用优先级队列（最大的在最上面）
- 第一步，累加整个数组，如果数组全部的数之和发现 <= 0，那么无论如何也走不出所有屋子，直接返回-1
- 第二步，遍历整个数组，遇到负数，压到优先级队列里，有种贪心的思想，将伤害血量最大的怪物总是想先挪到后面，这样再遇到后面的怪物时，更有优势（所以我们压栈时，可以压入负数的相反数，这样，最小的，放到队列里就是最大的）
- 遍历数组时，累加当前血量，如果发现此时血量小于等于0时，需要及时将负数移动到后面去，此时只需要将队列里的数据弹出来，相当于移动一次，然后加上队列里的数据（因为之前已经减过了）。
C++代码
class Solution {
public:
int magicTower(vector<int>& nums) {
using ll = long long;
ll sum = 1;
for(auto& i : nums){
sum += i;
}
if(sum <= 0){
return -1;
}
ll res = 0;
ll blood = 1;
priority_queue<int> q;
for(auto& i : nums){
if(i < 0){
q.push(-i);
}
blood += i;
while(blood <= 0){
res++;
blood += q.top();
q.pop();
}
}
return res;
}
};
