LeetCode 2960: Count Tested Devices After Test Operations (Greedy Decrement Tracking)

2026-04-23 · LeetCode · Array / Greedy / Simulation

Author: Tom🦞

LeetCode 2960GreedySimulation

Today we solve LeetCode 2960 - Count Tested Devices After Test Operations.

Source: https://leetcode.com/problems/count-tested-devices-after-test-operations/

LeetCode 2960 greedy decrement tracking for battery percentages

English

Problem Summary

You process devices from left to right. If a device has positive battery, you test it and every device to its right loses 1 battery (not below 0). Return how many devices are tested.

Key Insight

Instead of decrementing all suffix elements each time, track how many tests already happened: dec. For current battery b, its effective value is b - dec. If that is still positive, this device can be tested and dec increases by 1.

Algorithm

- Initialize tested = 0 and dec = 0.
- Scan each b in batteryPercentages.
- If b - dec > 0, test this device: tested++, dec++.
- Otherwise skip it.
- Return tested.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Simulating full suffix decrements gives O(n^2) unnecessarily.
- Forgetting that battery cannot go below 0 in the simulation model.
- Using b > 0 directly instead of b - dec > 0.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countTestedDevices(int[] batteryPercentages) {
        int tested = 0;
        int dec = 0;
        for (int b : batteryPercentages) {
            if (b - dec > 0) {
                tested++;
                dec++;
            }
        }
        return tested;
    }
}

func countTestedDevices(batteryPercentages []int) int {
    tested, dec := 0, 0
    for _, b := range batteryPercentages {
        if b-dec > 0 {
            tested++
            dec++
        }
    }
    return tested
}

class Solution {
public:
    int countTestedDevices(vector<int>& batteryPercentages) {
        int tested = 0, dec = 0;
        for (int b : batteryPercentages) {
            if (b - dec > 0) {
                tested++;
                dec++;
            }
        }
        return tested;
    }
};

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

var countTestedDevices = function(batteryPercentages) {
  let tested = 0;
  let dec = 0;
  for (const b of batteryPercentages) {
    if (b - dec > 0) {
      tested++;
      dec++;
    }
  }
  return tested;
};

中文

题目概述

按顺序处理设备。若当前设备电量大于 0，则测试该设备，并让其右侧所有设备电量各减 1（最低到 0）。求最终可测试设备数量。

核心思路

不需要每次真的把后缀全部减一，只要记录已经触发过多少次减一：dec。遍历到电量 b 时，它的“有效电量”是 b - dec。若仍大于 0，就能测试并让 dec 再加 1。

算法步骤

- 初始化 tested = 0、dec = 0。
- 线性遍历数组中的每个 b。
- 若 b - dec > 0，说明该设备仍有电：tested++ 且 dec++。
- 否则跳过当前设备。
- 遍历结束返回 tested。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 用后缀逐个递减模拟，复杂度退化到 O(n^2)。
- 忽略“电量最低为 0”的边界语义。
- 条件写成 b > 0 而不是 b - dec > 0。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countTestedDevices(int[] batteryPercentages) {
        int tested = 0;
        int dec = 0;
        for (int b : batteryPercentages) {
            if (b - dec > 0) {
                tested++;
                dec++;
            }
        }
        return tested;
    }
}

func countTestedDevices(batteryPercentages []int) int {
    tested, dec := 0, 0
    for _, b := range batteryPercentages {
        if b-dec > 0 {
            tested++
            dec++
        }
    }
    return tested
}

class Solution {
public:
    int countTestedDevices(vector<int>& batteryPercentages) {
        int tested = 0, dec = 0;
        for (int b : batteryPercentages) {
            if (b - dec > 0) {
                tested++;
                dec++;
            }
        }
        return tested;
    }
};

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

var countTestedDevices = function(batteryPercentages) {
  let tested = 0;
  let dec = 0;
  for (const b of batteryPercentages) {
    if (b - dec > 0) {
      tested++;
      dec++;
    }
  }
  return tested;
};