题目描述
公司老板做了一笔大生意，想要给每位员工分配一些奖金，想通过游戏的方式来决定每个人分多少钱。
按照员工的工号顺序，每个人随机抽取一个数字。按照工号的顺序往后排列。
遇到第一个数字比自己数字大的，那么，前面的员工就可以获得的奖金
如果遇不到比自己数字大的，就给自己分配随机数数量的奖金。
- 例如，按照工号顺序的随机数字是:
2, 10, 3
- 第
个员工的数字
比第
个员工的数字
- 第
- 第
个员工是最后一个员工，后面也没有比他更大数字的员工，所以他得到的奖金是
- 请帮老板计算一下每位员工最终分到的奖金都是多少钱。
输入描述
- 第一行
代表员工数量（包含最后一个老板）
- 第二行是每一位员工被分配到的随机数字
输出描述
- 最终每一位员工分到的奖金数量
备注：随机数字不重复，员工数量（包含老板）范围是[1, 10000]，随机数范围是[1, 100 000]
用例
--输入
3
2 10 3
--输出
8 10 3题目解析
- 对于每一个员工而言，其所能获得的奖金仅仅和其后面的员工相关。
- 那么可以从最后一个员工开始计算。对于当前的员工而言，要找到后面有没有比他数字更大的员工。那么可以用一个变量维护一个其后面员工所抽到的随机数字的最大值。
- 然后用一个队列维护出现的数据
- ex：
[9, 4, 5, 6, 8] - 遍历数字 8 ，最大值是 8，队列 为
[8] - 遍历到数字 6，最大值 8，队列为
[6, 8]
- 为什么 6 能入队，因为对于当前数字而言，要找第一个比 自己数字大的，所以，对于 数字5 而言，那么 数字6 是第一个比其大的数字
- 同理，遍历到数字 5，最大值 8，队列为
[5, 6, 8] - 同理，遍历到数字 4，最大值 8，队列位
[4, 5, 6, 8] - 遍历到数字 9，那么最大值是 9了，清空队列
[9]
- 为什么要清空，因为对于后续的数字，仅仅需要考虑数字 9 即可，因为其是最大的。
show code
package com.hw;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* desc : <a href="https://fcqian.blog.csdn.net/article/details/128385677">分奖金</a>
* <p>
* create time : 2023/7/22 20:47
*/
public class BonusMaster {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] bonus = new int[n];
for (int i = 0; i < n; i++) {
bonus[i] = in.nextInt();
}
bonusMaster(bonus, n);
}
private static void bonusMaster(int[] bonus, int n) {
// 记录每一个员工分到的奖金数额
int[] ans = new int[n];
// 记录一个当前出现的最大随机数
int maxNum = 0;
// 队列保存出现过的数字，第一个元素保存 随机数，第二个元素保存对应的索引下标
PriorityQueue<Integer[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
// 倒着遍历
for (int i = n - 1; i >= 0; i--) {
// 拿到当前员工所代表的随机数, i 是当前员工所代表的下标
int local = bonus[i];
// 开始判断，其后面有没有比它本身大的 随机数
if(local < maxNum) {
// 如果有的话，从队列中.
while(!queue.isEmpty()) {
Integer[] peek = queue.peek();
if(peek[0] > local) {
// 找到了第一个比其大的数字，直接计算
ans[i] = (peek[1] - i) * (peek[0] - local);
// 当前元素入队
queue.offer(new Integer[]{local, i});
break;
} else {
queue.poll();
}
}
} else {
// 如果没有的话，随机数作为奖金数量.
ans[i] = local;
// 当前元素入队列，并清空队列
queue.clear();
// 0：随机数值， i：对应数组下标.
queue.offer(new Integer[]{local, i});
// 更新最大值
maxNum = local;
}
}
for (int an : ans) {
System.out.print(an);
System.out.print(" ");
}
}
}