题解 | #牛牛打怪兽#的Python解法

1. 解题思路

首先注意题目描述里的几个关键点：

“当使用这个组合拳的时候，打第X怪兽的时候，同时会打到第2X、2X+1这两个怪兽，每次组合拳会扣打到的怪兽一滴血。” 和“值得注意的是组合拳必须攻击三只怪兽。” 这两句话告诉我们，一套组合拳是要打在3个怪兽身上，而且只有奇数个怪兽的时候才会生效，怪兽数量小于3 或者为偶数个怪兽，都不会生效！同时每个怪兽的掉血是呈 -1 的递减趋势。
“一个怪兽血量为0即为死亡，同时组合拳是可以鞭尸的，这意味着即使怪兽死亡，也可以对其使用组合拳。” 第二句话则告诉我们怪兽的终止条件是血量为0，且即便其中一只为0也可以继续打怪兽，直到三只都为0。

所以这里可以采用贪心算法的思想来解此题，首先我们找到中间那只怪兽、最后一只怪兽以及倒数第二只怪兽作为最大区间，然后往前不断迭代，缩小区间范围直到最小区间；最后的总攻击次数 = 前面累加的攻击次数 + 最小区间的攻击次数。
下面再图解两个示例加深理解，首先看奇数个怪兽的整个组合拳过程：

第一步，找到整个怪兽个数的中间点和它的最大区间，然后获得第一次攻击次数：
第二步，开始往前缩小区间，更新中间点，并获得第二次攻击次数：
第三步，重复前面的步骤直到只剩一只怪兽：
最后一步，累加前面的攻击次数，再加上最后一只怪兽的次数就是总攻击次数：

PS：当怪兽个数为偶数的时候是这样的：
图片说明

2. 核心代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 n个怪兽
# @param A int整型一维数组 A数组代表每个怪兽的血量
# @return int整型
#
class Solution:
    def slove(self , n , A ):
        # write code here
        #第一种情况，当怪兽数量小于3的时候或怪兽数量为偶数时，返回-1
        if (n < 3) or (n & 1 == 0):
            return -1
        #首先定义最后的总攻击数的初始值
        num = 0
        #当怪兽数量大于等于3，且为奇数时：
        for i in range(n-2, 0, -2):
            #找到最中间那只怪兽，然后会攻击倒数第二只和最后一只怪兽，此时区间最大
            times = max(0, A[i], A[i+1])
            #每次攻击三只怪兽后，不断更新中间点，缩小区间
            A[i//2] -= times
            A[i] -= times
            A[i+1] -= times
            #累加每三只怪兽的总攻击次数
            num += times
        #最后当怪兽只剩一个的时候，直接用前面的总攻击数+ 剩余这个怪兽的血量（即攻击次数） 就是最后所求
        total = num + max(A[0], 0) 
        return total

3. 复杂度分析

时间复杂度： $O(n)$ (只需遍历一次怪兽数组的长度，每次都是 $n/2$ )
空间复杂度： $O(1)$ (无额外的空间使用）

--------------------------------------------------------我是解法二的分割线--------------------------------------------------------

4. 解法二

4.1 思路

此题还可以从怪兽的剩余血量这个角度入手：

先找到最后一只和倒数第二只的怪兽血量并比较他们的大小，找出血量较大的那只；
然后找到初始中间点的怪兽，与较大那只怪兽血量相比较，如果初始怪兽的血量低于较大那只，即初始=0；
否则，初始大于较大那只，用初始减去较大怪兽血量，得到剩余血量；
一直递归上面这个过程，累加上面的血量，直到只剩最开始那只怪兽的剩余血量（也就是递归的终止条件）；
最后累加的血量+最开始怪兽的剩余血量就是最终攻击数。

4.2 核心代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 n个怪兽
# @param A int整型一维数组 A数组代表每个怪兽的血量
# @return int整型
#
class Solution:
    def slove(self , n , A ):
        # write code here
        #第一种情况，当怪兽数量小于3的时候或怪兽数量为偶数时，返回-1
        if (n < 3) or (n & 1 == 0):
            return -1
        #首先定义最后的总攻击数的初始值
        num = 0
        #当怪兽数量大于等于3，且为奇数时：
        for i in range((n//2) -1, -1, -1):
            #首先找到最后两只怪兽，比较他们的血量大小
            times = max(A[2*i + 1], A[2*i + 2])
            #比较当前中间怪兽血量与末尾较大那只的血量大小
            A[i] = max(0, A[i] - times) 
            #递归，累加怪兽的血量
            num += times
        #递归终止条件：当怪兽只剩最开始那只时；
        #最后直接用前面的总攻击数+ 剩余这个怪兽的血量（即攻击次数） 就是最后所求
        total = num + A[0]
        return total

4.3 复杂度分析

时间复杂度： $O(n)$ (一共递归了 $n/2$ 次)
空间复杂度： $O(n)$ (递归的空间占用为 $n/2$ )