如题:
LCP 30. 魔塔游戏
思路
参考力扣的大佬的思路,使用贪心算法解决
- 如果每个房间的血量加起来小于0,那么无解,返回-1即可;
- 我们使用先进先出的队列,来保存导致血量减小的房间(值);
a). 当blood加当前层小于0,则表示当前层需要移动到最后,step加一,同时还原原血量; - 遍历nums完成,则step为需要移动的房间数。
代码
public int magicTower(int[] nums) {
int sum = 0;
for (int temp : nums) {
sum += temp;
}
if (sum < 0) {
return -1;
}
int step = 0;
long blood = 0;
Queue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] < 0) {
queue.offer(nums[i]);
if (blood + nums[i] < 0) {
// 移动次数加1
step ++;
// 血量还原
blood -= queue.poll();
}
}
// 执行到这,表示血量不会小于0,直接累加即可
blood += nums[i];
}
return step;
}
网友评论