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.5 美元。
接下来 7 - 3 = 4 美元按 10% 的税率征税：4 * 10% = 0.4 美元。
最后 10 - 7 = 3 美元按 25% 的税率征税：3 * 25% = 0.75 美元。
需要缴纳的税款总额是 1.5 + 0.4 + 0.75 = 2.65 美元。

示例 2：

输入：brackets = [[1,0],[4,25],[5,50]], income = 2
输出：0.25000
解释：
前 1 美元按 0% 的税率征税：1 * 0% = 0 美元。
接下来 2 - 1 = 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 。

解题思路

这道题是一个经典的税率计算模拟题，需要理解累进税制的概念。

核心思路：

累进税制是指不同收入区间适用不同的税率。我们需要逐个税级计算应缴税款，然后累加得到总税款。

算法步骤：

  1. 维护一个 prev 变量记录前一个税级的上限，初始为 0
  2. 遍历每个税级 [upper, percent]
  3. 计算当前税级的应税收入：min(income, upper) - prev
    • 如果收入超过当前上限，则该税级的应税收入为 upper - prev
    • 如果收入未达到当前上限，则该税级的应税收入为 income - prev
  4. 计算当前税级的税款：应税收入 × 税率 / 100
  5. 更新 prev = upper，继续处理下一税级
  6. 如果 income <= upper，说明后续税级都不会产生税款，可以提前结束

时间复杂度分析：

最坏情况下需要遍历所有税级，但实际上当收入不超过某个税级上限时可以提前结束，平均情况较好。

代码实现

class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        double tax = 0.0;
        int prev = 0;
        
        for (auto& bracket : brackets) {
            int upper = bracket[0];
            int percent = bracket[1];
            
            int taxableIncome = min(income, upper) - prev;
            tax += taxableIncome * percent / 100.0;
            
            if (income <= upper) break;
            prev = upper;
        }
        
        return tax;
    }
};

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

public class Solution {
    public double CalculateTax(int[][] brackets, int income) {
        double tax = 0.0;
        int prev = 0;
        
        foreach (var bracket in brackets) {
            int upper = bracket[0];
            int percent = bracket[1];
            
            int taxableIncome = Math.Min(income, upper) - prev;
            tax += taxableIncome * percent / 100.0;
            
            if (income <= upper) break;
            prev = upper;
        }
        
        return tax;
    }
}

var calculateTax = function(brackets, income) {
    let tax = 0;
    let prev = 0;
    
    for (const [upper, percent] of brackets) {
        const taxableIncome = Math.min(income, upper) - prev;
        tax += taxableIncome * percent / 100;
        
        if (income <= upper) break;
        prev = upper;
    }
    
    return tax;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是税级数量。最坏情况需要遍历所有税级，但通常可以提前结束
空间复杂度O(1)，只使用常数额外空间