统计已测试设备

难度: Easy

给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages ，表示 n 个设备的电池百分比。

你的任务是按照顺序测试每个设备 i，执行以下测试操作：

如果 batteryPercentages[i] 大于 0：
- 增加已测试设备的计数。
- 将下标在 [i + 1, n - 1] 的所有设备的电池百分比减少 1，确保它们的电池百分比 不会低于 0 ，即 batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。
- 移动到下一个设备。
否则，移动到下一个设备而不执行任何测试。

返回一个整数，表示按顺序执行测试操作后 已测试设备 的数量。

示例 1：

输入：batteryPercentages = [1,1,2,1,3]
输出：3
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [1,0,1,0,2] 。
在设备 1 上，batteryPercentages[1] == 0 ，移动到下一个设备而不进行测试。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 变为 [1,0,1,0,1] 。
在设备 3 上，batteryPercentages[3] == 0 ，移动到下一个设备而不进行测试。
在设备 4 上，batteryPercentages[4] > 0 ，现在有 3 个已测试设备，batteryPercentages 保持不变。
因此，答案是 3 。

示例 2：

输入：batteryPercentages = [0,1,2]
输出：2
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] == 0 ，移动到下一个设备而不进行测试。
在设备 1 上，batteryPercentages[1] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [0,1,1] 。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 保持不变。
因此，答案是 2 。

提示：

1 <= n == batteryPercentages.length <= 100
0 <= batteryPercentages[i] <= 100

Submission

运行时间: 27 ms

内存: 16.2 MB

class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        dec = 0
        for x in batteryPercentages:
            if x > dec:
                dec += 1
        return dec

Explain

题解中使用了一个变量 `dec` 来模拟电池百分比的递减操作。对于数组中的每个元素 `x`，如果 `x` 大于 `dec`，说明设备仍有足够的电量进行测试。随后将 `dec` 增加 1，模拟对后续设备的电池百分比递减。通过这种方式，可以在一次遍历中统计能够被测试的设备数量。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        dec = 0  # 初始化递减变量
        tested_count = 0  # 初始化已测试设备的计数
        for x in batteryPercentages:  # 遍历所有设备的电池百分比
            if x > dec:  # 如果当前设备的电池百分比大于递减值
                tested_count += 1  # 增加已测试设备的计数
                dec += 1  # 增加递减值，模拟后续设备电池百分比的减少
        return tested_count  # 返回已测试设备的总数

Explore

使用递增的单个变量`dec`来模拟每个设备电池百分比的递减，而不是实际修改数组中的值，主要是为了简化问题处理和提高算法效率。这种方法避免了修改原始数据，使得算法具有更好的时间复杂度（O(n)），因为仅需遍历一次数组。此外，这种方式也减少了空间复杂度，因为不需要额外的存储空间来保存修改后的电池百分比。

题解中的方法没有直接处理数组中可能存在的负数值。理论上，电池百分比不应该是负数，这可能表示输入数据异常或错误。如果要严格处理输入验证，算法应该首先检查每个元素是否非负，若发现负数则可以忽略该设备或抛出一个错误信息。

根据题解中的逻辑，如果电池百分比`x`等于递减值`dec`，则该设备不会被测试，因为条件是`x > dec`。这可能与题目的具体要求有所不符，视具体题目描述而定。如果题目要求当电池百分比大于等于递减值时设备仍可测试，那么条件应修改为`x >= dec`。

是的，`dec`变量的递增正确地模拟了题目中描述的电池消耗逻辑。通过逐步增加`dec`值，算法模拟了每次测试一个设备后，所有后续设备的电池百分比相对前一个设备减少1的效果。这种模拟方式有效地反映了设备电池百分比的递减，而无需直接修改原数组。