语言月赛 202411 Phoenix
题目分析¶
给定 $n$ 个宝宝及其上进心 $a_1, a_2, \ldots, a_n$， 年龄为 $n$ 的宝宝一定是好宝宝； 其他宝宝只有当其上进心严格大于所有年龄比它大的宝宝的上进心时，才是好宝宝。
解题思路¶
- 对于每个宝宝 $i$（$1 \leq i \leq n-1$）， 遍历所有年龄比它大的宝宝（即 $j > i$）， 判断 $a_i$ 是否严格大于所有这些 $a_j$；
- 如果满足，计数器加 $1$；
- 年龄为 $n$ 的宝宝直接计入计数器。
实现步骤¶
- 外层循环遍历 $i$，
for (int i = 1; i < n; i++)无需遍历到 $n$，第 $n$ 个一定是好宝宝； - 使用标记变量打标记，初始化
ok设为 $1$； - 内层循环遍历 $j$，
for (int j = i + 1; j <= n; j++)。遍历年龄更大的宝宝。 - 若存在
a[i] <= a[j]，说明上进心低于年龄更大的。此时更新ok为 $0$。 - 根据内层循环结束后
ok的值来进行计数即可。
复杂度分析¶
- 时间复杂度：$O(n^2)$，双重循环遍历；
- 空间复杂度：$O(n)$，存储输入数组。
总结¶
- 暴力解法简单直观，易于实现；
- 适合小规模数据，性能较差，不适合大数据；
- 通过优化（例如从后向前遍历维护最大值）可以提升至 $O(n)$。