计算应缴税款总额【LC2303】

You are given a 0-indexed 2D integer array brackets where brackets[i] = [upperi, percenti] means that the ith tax bracket has an upper bound of upperi and is taxed at a rate of percenti. The brackets are sorted by upper bound (i.e. upperi-1 < upperi for 0 < i < brackets.length).

Tax is calculated as follows:

• The first upper0 dollars earned are taxed at a rate of percent0.
• The next upper1 - upper0 dollars earned are taxed at a rate of percent1.
• The next upper2 - upper1 dollars earned are taxed at a rate of percent2.
• And so on.

You are given an integer income representing the amount of money you earned. Return the amount of money that you have to pay in taxes. Answers within 10-5 of the actual answer will be accepted.

想每天九点起床

I guess Peter Pan was right

Growing up’s a waste of time

So I think I’ll fly away

Set a course for brighter days

• 思路：直接遍历税率数组直到income遇到上限值，梯度计算税额，使用变量记录前一档税额的上限值pre

。若income<=bracket[0]，那么表示income遇到上限值，该段金额产生的税率为(income−pre)∗bracket[1]/100

。若income>bracket[0]，那么表示该段金额产生的上限为税率为bracket[0]，(bracket[0]−pre)∗bracket[1]/100

• 实现

class Solution {
    public double calculateTax(int[][] brackets, int income) {
        double res = 0;
        int n = brackets.length;
        int pre = 0;
        for (int[] bracket : brackets){
            if (income <= bracket[0]) {
                res += (income - pre) * bracket[1] / 100.0;
                break;
            }else {
                res += (bracket[0] - pre) * bracket[1] / 100.0;
                pre = bracket[0];
            }
        }
        return res;
    }
}

。复杂度

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