教育中介公司网站建设费用,能够沟通业务的网站,广东seo推广,网站原型图设计【LetMeFly】LCP 30.魔塔游戏#xff1a;贪心#xff08;优先队列#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/p0NxJO/
小扣当前位于魔塔游戏第一层#xff0c;共有 N 个房间#xff0c;编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于…【LetMeFly】LCP 30.魔塔游戏贪心优先队列
力扣题目链接https://leetcode.cn/problems/p0NxJO/
小扣当前位于魔塔游戏第一层共有 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
方法一贪心优先队列
使用一个优先队列pq记录所有的负数房间绝对值越大的负数房间越优先出栈从前到后遍历所有房间并将房间的值累加到自己的血量上若房间值为负记得加入优先队列。
一旦遇到自己的血量不为正数的情况就开始反悔将队列中绝对值最大的负数房间调整到队尾血量恢复这个房间的绝对值的量并记录一共有多少房间移动到了队列尾。
一旦出现血量非正且队列为空的情况立刻返回-1。若遍历结束看血量是否大于移动到队尾的所有房间绝对值之和。
时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))空间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))
AC代码
C
class Solution {
public:int magicTower(vectorint nums) {priority_queueint pq;long long now 1;long long totalNegative 0;int ans 0;for (int t : nums) {if (t 0) {pq.push(-t);}now t;while (now 0 pq.size()) {int thisNegative pq.top();pq.pop();now thisNegative;totalNegative thisNegative;ans;}if (now 0) {return -1;}}return now totalNegative ? ans : -1;}
};Python
# from typing import List
# import heapqclass Solution:def magicTower(self, nums: List[int]) - int:pq []now 1totalNegative 0ans 0for t in nums:if t 0:heapq.heappush(pq, t)now twhile now 0 and pq:thisNegative -heapq.heappop(pq)totalNegative thisNegativenow thisNegativeans 1if now 0:return -1return ans if now totalNegative else -1 同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136053198
