P2656. 分奖金

解题思路

每一个员工本质上是要找到位于其右边第一个大于它的元素，并且求出它们之间的大小差值和距离差值。显然应该立刻想到使用单调栈来完成。

无论是正序还是逆序，都可以完成这个题目。

单调栈的具体模板和分析可以详见正课内容或者2024/06/22 真题讲解（单调栈专题）。

代码

解法一：逆序遍历

思路展开 代码采用逆序遍历的单调栈写法，从最后一名员工往前处理。

• ans 用 Arrays.copyOf(nums, n) 初始化为每个人自己抽到的数字：这直接实现了题面「后面没有比自己数字大的同事，就拿自己抽到的数字」的规则，右边找不到更大数字的位置无需再单独处理。
• 单调栈里存的是下标而不是数值（栈底到栈顶对应的数值递减）。处理第 i 个员工时，先把栈顶所有「数值小于等于 num」的下标弹掉——它们不可能是 i 右边第一个严格更大的数字；弹完后如果栈非空，栈顶下标 stack.peek() 对应的就是 i 右边最近的、严格比 num 大的数字。
• 奖金按题面公式「距离 × 数字差值」计算：ans[i] = (stack.peek() - i) * (nums[stack.peek()] - num)，正因为要同时用到下标差和数值差，栈里才必须存下标。
• 最后把当前下标 i 压栈，供左边的员工继续比较。

复杂度分析 设员工人数为 n。

• 时间复杂度：O(n)。逆序遍历每个下标恰好一次；每个下标至多入栈一次、被弹出一次，while 弹栈的总次数不超过 n，所以两层循环的总工作量是摊还线性的。
• 空间复杂度：O(n)，包括单调栈（最坏情况保留全部下标）和答案数组 ans。

边界与注意事项

• 出栈条件是 num >= nums[stack.peek()]：数字相等不算「更大」，必须严格大于才能结算奖金，等值的栈顶会被直接弹掉。
• 最后一名员工处理时栈为空，不会进入结算分支，按初始化拿自己抽到的数字，与题面例子中第 3 个同事得 3 的情形一致；n = 1 时同理，唯一的员工输出自己的数字。
• 输出格式：数字之间用单个空格分隔，行尾没有多余空格（代码里 i > 0 时才先打印空格）。