计算应缴税款总额

标签: 数组 模拟

难度: Easy

给你一个下标从 0 开始的二维整数数组 brackets ，其中 brackets[i] = [upperi, percenti] ，表示第 i 个税级的上限是 upperi ，征收的税率为 percenti 。税级按上限 从低到高排序（在满足 0 < i < brackets.length 的前提下，upperi-1 < upperi）。

税款计算方式如下：

  • 不超过 upper0 的收入按税率 percent0 缴纳
  • 接着 upper1 - upper0 的部分按税率 percent1 缴纳
  • 然后 upper2 - upper1 的部分按税率 percent2 缴纳
  • 以此类推

给你一个整数 income 表示你的总收入。返回你需要缴纳的税款总额。与标准答案误差不超 10-5 的结果将被视作正确答案。

示例 1：

输入：brackets = [[3,50],[7,10],[12,25]], income = 10
输出：2.65000
解释：
前 $3 的税率为 50% 。需要支付税款 $3 * 50% = $1.50 。
接下来 $7 - $3 = $4 的税率为 10% 。需要支付税款 $4 * 10% = $0.40 。
最后 $10 - $7 = $3 的税率为 25% 。需要支付税款 $3 * 25% = $0.75 。
需要支付的税款总计 $1.50 + $0.40 + $0.75 = $2.65 。

示例 2：

输入：brackets = [[1,0],[4,25],[5,50]], income = 2
输出：0.25000
解释：
前 $1 的税率为 0% 。需要支付税款 $1 * 0% = $0 。
剩下 $1 的税率为 25% 。需要支付税款 $1 * 25% = $0.25 。
需要支付的税款总计 $0 + $0.25 = $0.25 。

示例 3：

输入：brackets = [[2,50]], income = 0
输出：0.00000
解释：
没有收入，无需纳税，需要支付的税款总计 $0 。

提示：

  • 1 <= brackets.length <= 100
  • 1 <= upperi <= 1000
  • 0 <= percenti <= 100
  • 0 <= income <= 1000
  • upperi 按递增顺序排列
  • upperi 中的所有值 互不相同
  • 最后一个税级的上限大于等于 income

Submission

运行时间: 25 ms

内存: 16.1 MB

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        totalTax = lower = 0
        for upper, percent in brackets:
            tax = (min(income, upper) - lower) * percent
            totalTax += tax
            if income <= upper:
                break
            lower = upper
        return totalTax / 100

Explain

此题解采用了逐级累计的方法来计算税款。对于每一个税级，计算当前税级的应税收入（即当前税级的上限与前一税级的上限之差，且不超过总收入），然后乘以该税级的税率，得到该税级的税款。累加各税级的税款得到总税款。当总收入小于或等于当前税级的上限时，意味着后续税级无需计算，可以提前终止循环。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        totalTax = lower = 0 # 初始化总税款和上一税级的上限
        for upper, percent in brackets: # 遍历每个税级
            tax = (min(income, upper) - lower) * percent # 计算当前税级的税款
            totalTax += tax # 累加税款
            if income <= upper: # 如果收入小于等于当前税级上限，终止循环
                break
            lower = upper # 更新上一税级的上限
        return totalTax / 100 # 返回总税款，注意除以100转换为小数

Explore

在题解中，循环的结束条件是当收入值`income`小于或等于当前税级的上限`upper`时。这是因为税级是逐级递增的，一旦收入在某个税级范围内，更高的税级就不会再对收入产生影响。因此，一旦达到这个条件，程序就可以提前终止循环，因为后续的税级不会再对总税款有贡献。

使用`min(income, upper) - lower`是为了确保计算的收入部分不会超过当前税级的上限。如果直接使用`income`而不是`min(income, upper)`，当收入超过当前税级的上限时，会导致计算出的应税收入超出实际应税的范围，从而计算出错误的税款。例如，如果收入为40000，而当前税级的上限是30000，直接使用income将计算出高于30000的税，这是不正确的。`min`函数确保不会超过税级上限，从而保证税款计算的正确性。

在计算完一个税级后更新`lower`为当前税级的`upper`是为了为计算下一个税级的应税收入做准备。`lower`代表的是上一个处理过的税级的上限，它被用作计算下一个税级应税收入的下界。这种更新确保了每个税级只计算超过前一个税级上限的收入部分，防止对同一部分收入重复计算税款。

在题解中，所有税款最后除以100的操作是为了将税率的百分比形式转化为小数形式。税率在题解中是以百分比的形式给出的（例如10表示10%），因此计算税款时首先以百分比形式计算，最后通过除以100将这个百分比转换为相应的小数（即10%变为0.10）。这样做是为了正确计算出以货币单位表示的税款金额。