3616. 学生替换人数 🔒

题目描述

给定一个整数数组 ranks，其中 ranks[i] 表示第 i 个 按顺序 到达的学生排名。数字越低表示排名越好。

最初，默认选中第一个学生。

当一名排名严格更好的学生到来时，会发生替换，并取代当前的选择。

返回替换的总数。

示例 1：

输入：ranks = [4,1,2]

输出：1

解释：

第一个 ranks[0] = 4 的学生最初被选中。
第二个学生 ranks[1] = 1 比当前选择更好，因此发生替换。
第三名学生排名更差，因此没有发生替换。
因此，替换的人数为 1。

示例 2：

输入：ranks = [2,2,3]

输出：0

解释：

第一个 ranks[0] = 2 的学生最初被选中。
两个 ranks[1] = 2 或 ranks[2] = 3 都不如当前选择好。
因此，替换的人数为 0。

提示：

1 <= ranks.length <= 10⁵
1 <= ranks[i] <= 10⁵

解法

方法一：模拟

我们用一个变量 \(\text{cur}\) 来记录当前选中的学生的排名。遍历数组 \(\text{ranks}\)，如果遇到一个排名更好的学生（即 \(\text{ranks}[i] < \text{cur}\)），则更新 \(\text{cur}\) 并将答案加一。

遍历结束后，返回答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是学生的数量。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def totalReplacements(self, ranks: List[int]) -> int:
        ans, cur = 0, ranks[0]
        for x in ranks:
            if x < cur:
                cur = x
                ans += 1
        return ans

class Solution {
    public int totalReplacements(int[] ranks) {
        int ans = 0;
        int cur = ranks[0];
        for (int x : ranks) {
            if (x < cur) {
                cur = x;
                ++ans;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int totalReplacements(vector<int>& ranks) {
        int ans = 0;
        int cur = ranks[0];
        for (int x : ranks) {
            if (x < cur) {
                cur = x;
                ++ans;
            }
        }
        return ans;
    }
};

func totalReplacements(ranks []int) (ans int) {
    cur := ranks[0]
    for _, x := range ranks {
        if x < cur {
            cur = x
            ans++
        }
    }
    return
}

function totalReplacements(ranks: number[]): number {
    let [ans, cur] = [0, ranks[0]];
    for (const x of ranks) {
        if (x < cur) {
            cur = x;
            ans++;
        }
    }
    return ans;
}

3616. 学生替换人数 🔒

题目描述

解法

方法一：模拟

评论