题目描述与示例

题目描述

公司老板做了一笔大生意，想要给每位员工分配一些奖金，想通过游戏的方式来决定每个人分多少钱。

按照员工的工号顺序，每个人随机抽取一个数字。按照工号的顺序往后排列，遇到第一个数字比自己数字大的，那么，前面的员工就可以获得**“距离数字差值”**的奖金。如果遇不到比自己数字大的，就给自己分配随机数数量的奖金。

例如，按照工号顺序的随机数字是：2,10,3。那么第2个员工的数字10比第1个员工的数字2大，所以，第1个员工可以获得1*(10-2)=8。第2个员工后面没有比他数字更大的员工，所以，他获得他分配的随机数数量的奖金，就是10。第3个员工是最后一个员工，后面也没有比他更大数字的员工，所以他得到的奖金是3。

请帮老板计算一下每位员工最终分到的奖金都是多少钱。

题目练习地址：https://www.algomooc.com/problem/P2656

输入描述

第一行n表示员工数量

第二是每位员工分配的随机数字

输出描述

最终每位员工分到的奖金数量

注：随机数字不重复，员工数量范围1~10000，随机数范围1~100000

示例

输入

3
2 10 3

输出

8 10 3

解题思路

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

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

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

代码

解法一：逆序遍历

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 免费获取华为 OD 笔试真题题库和视频

# 输入表示n个操作的数组ops
ops = input().split(" ")

stack = list()      # 初始化一个空栈，在python中可以用list表示栈
isError = False     # 用于标记是否出现异常的标志，初始化为False表示没有异常

for record in ops:  # 遍历整个ops数组
    # 若record为数字，则直接将该数字加入栈中，注意要将str转为int
    if record != 'D' and record != 'C' and record != '+':
        stack.append(int(record))
    # 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
    elif record == 'D' and len(stack) >= 1:
        stack.append(stack[-1] * 2)
    # 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
    elif record == 'C' and len(stack) >= 1:
        stack.pop()
    # 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值
    elif record == '+' and len(stack) >= 2:
        stack.append(stack[-1] + stack[-2])
    # 如果不满足上述的任何条件，说明出现了异常，
    # 将isError修改为True，同时直接退出循环
    else:
        isError = True
        break

# 如果出现异常，输出-1
# 如果没有异常，输出整个栈中数字的总和
print(-1 if isError else sum(stack))


# 输入员工个数n
n = int(input())
# 输入N个员工的随机数数组
nums = list(map(int, input().split()))

# 构建一个单调栈，用来存放不同随机数的索引
# 栈中储存的索引所对应在height中的元素大小，从栈底至栈顶单调递减
# 即更大的数（的下标）位于栈底
stack = list()

# 构建列表ans，用来保存输出结果
# 初始化其中所有的元素和原数组一样，注意此处要使用拷贝
ans = nums.copy()

# 逆序遍历nums中的每一个随机数
for i in range(n-1, -1, -1):
    num = nums[i]
    # 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
    # 如果栈顶元素存在并且num【大于等于】栈顶元素stack[-1]这个下标对应的数字
    # 说明栈顶元素stack[-1]这个下标对的数字，并不是随机数num右边最近的比num更大的元素
    # 需要将栈顶元素弹出，继续寻找比num大的栈顶元素
    while len(stack) > 0 and num >= nums[stack[-1]]:
        # 栈顶元素下标对应的数字不大于当前数字num，不是符合要求的更大数字，弹出
        stack.pop()
    # 完成弹出后，如果栈顶仍存在元素，说明stack[-1]所对应的数字，是严格比当前数字num大的下一个数字
    if len(stack) > 0:
        # stack[-1]即为i这个索引所对应的，下一个最近的更大的随机数的下标
        # 它们之间的下标距离为stack[-1]-i，数字大小差值为nums[stack[-1]]-num
        # 相乘后在ans中修改，作为答案
        ans[i] = (stack[-1]-i)*(nums[stack[-1]]-num)

    # 再把当前下标i储存入栈中
    # 注意：所储存的是下标i，而不是随机数num
    stack.append(i)


# ans中的int元素转成str后才能合并成字符串
print(" ".join(map(str, ans)))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象用于输入
        Scanner sc = new Scanner(System.in);

        // 输入员工个数n
        int n = sc.nextInt();

        // 输入N个员工的随机数数组
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        // 构建一个单调栈，用来存放不同随机数的索引
        // 栈中储存的索引所对应在nums中的元素大小，从栈底至栈顶单调递减
        // 即更大的数（的下标）位于栈底
        Stack<Integer> stack = new Stack<>();

        // 构建列表ans，用来保存输出结果
        // 初始化其中所有的元素和原数组一样，注意此处要使用拷贝
        int[] ans = Arrays.copyOf(nums, n);

        // 逆序遍历nums中的每一个随机数
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];

            // 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
            // 如果栈顶元素存在并且num【大于等于】栈顶元素stack[-1]这个下标对应的数字
            // 说明栈顶元素stack[-1]这个下标对的数字，并不是随机数num右边最近的比num更大的元素
            // 需要将栈顶元素弹出，继续寻找比num大的栈顶元素
            while (!stack.isEmpty() && num >= nums[stack.peek()]) {
                // 栈顶元素下标对应的数字不大于当前数字num，不是符合要求的更大数字，弹出
                stack.pop();
            }

            // 完成弹出后，如果栈顶仍存在元素，说明stack[-1]所对应的数字，是严格比当前数字num大的下一个数字
            if (!stack.isEmpty()) {
                // stack.peek()即为i这个索引所对应的，下一个最近的更大的随机数的下标
                // 它们之间的下标距离为stack.peek()-i，数字大小差值为nums[stack.peek()]-num
                // 相乘后在ans中修改，作为答案
                ans[i] = (stack.peek() - i) * (nums[stack.peek()] - num);
            }

            // 再把当前下标i储存入栈中
            // 注意：所储存的是下标i，而不是随机数num
            stack.push(i);
        }

        // 输出结果，确保数字之间用空格分隔，没有尾部空格
        for (int i = 0; i < n; i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(ans[i]);
        }
        System.out.println();
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    // 输入员工个数n
    int n;
    cin >> n;

    // 输入N个员工的随机数数组
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    // 构建一个单调栈，用来存放不同随机数的索引
    // 栈中储存的索引所对应在nums中的元素大小，从栈底至栈顶单调递减
    // 即更大的数（的下标）位于栈底
    stack<int> s;

    // 构建列表ans，用来保存输出结果
    // 初始化其中所有的元素和原数组一样，注意此处要使用拷贝
    vector<int> ans = nums;

    // 逆序遍历nums中的每一个随机数
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];

        // 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
        // 如果栈顶元素存在并且num【大于等于】栈顶元素stack[-1]这个下标对应的数字
        // 说明栈顶元素stack[-1]这个下标对的数字，并不是随机数num右边最近的比num更大的元素
        // 需要将栈顶元素弹出，继续寻找比num大的栈顶元素
        while (!s.empty() && num >= nums[s.top()]) {
            // 栈顶元素下标对应的数字不大于当前数字num，不是符合要求的更大数字，弹出
            s.pop();
        }

        // 完成弹出后，如果栈顶仍存在元素，说明stack[-1]所对应的数字，是严格比当前数字num大的下一个数字
        if (!s.empty()) {
            // s.top()即为i这个索引所对应的，下一个最近的更大的随机数的下标
            // 它们之间的下标距离为s.top()-i，数字大小差值为nums[s.top()]-num
            // 相乘后在ans中修改，作为答案
            ans[i] = (s.top() - i) * (nums[s.top()] - num);
        }

        // 再把当前下标i储存入栈中
        // 注意：所储存的是下标i，而不是随机数num
        s.push(i);
    }

    // 输出结果，确保数字之间用空格分隔，没有尾部空格
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// 定义一个栈的数据结构
#define MAX_SIZE 100000
int stack[MAX_SIZE];
int top = -1;

// 向栈中压入元素
void push(int index) {
    stack[++top] = index;
}

// 从栈中弹出元素
int pop() {
    return stack[top--];
}

// 查看栈顶元素
int peek() {
    return stack[top];
}

int main() {
    int n;
    
    // 输入员工个数n
    scanf("%d", &n);

    // 输入N个员工的随机数数组
    int nums[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    // 构建数组ans，用来保存输出结果
    int ans[n];
    for (int i = 0; i < n; i++) {
        ans[i] = nums[i];
    }

    // 逆序遍历nums中的每一个随机数
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];

        // 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
        while (top >= 0 && num >= nums[stack[top]]) {
            // 弹出栈顶元素
            pop();
        }

        // 如果栈顶仍存在元素，说明stack[top]所对应的数字，是严格比当前数字num大的下一个数字
        if (top >= 0) {
            ans[i] = (stack[top] - i) * (nums[stack[top]] - num);
        }

        // 把当前下标i储存入栈中
        push(i);
    }

    // 输出结果，确保数字之间用空格分隔，没有尾部空格
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", ans[i]);
    }
    printf("\n");

    return 0;
}

Node JavaScript

const readline = require('readline');

// 创建接口读取输入
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

// 读取输入
rl.question('', (n) => {
    rl.question('', (line) => {
        const nums = line.split(' ').map(Number);
        const ans = [...nums];  // 拷贝一份nums数组

        // 单调栈
        const stack = [];

        // 逆序遍历
        for (let i = n - 1; i >= 0; i--) {
            const num = nums[i];

            // 比较栈顶元素与当前num的大小
            while (stack.length > 0 && num >= nums[stack[stack.length - 1]]) {
                stack.pop();
            }

            // 如果栈顶仍然有元素，说明栈顶对应的数字是比当前num大的下一个数字
            if (stack.length > 0) {
                ans[i] = (stack[stack.length - 1] - i) * (nums[stack[stack.length - 1]] - num);
            }

            // 将当前下标i压入栈中
            stack.push(i);
        }

        // 输出结果，确保数字之间用空格分隔，且没有尾部空格
        console.log(ans.join(' '));

        rl.close();  // 关闭接口
    });
});

Go

package main

import (
    "fmt"
)

func main() {
    var n int
    // 输入员工个数n
    fmt.Scan(&n)

    // 输入N个员工的随机数数组
    nums := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&nums[i])
    }

    // 构建一个单调栈
    stack := []int{}
    ans := make([]int, n)
    copy(ans, nums)  // 初始化结果数组

    // 逆序遍历nums中的每一个随机数
    for i := n - 1; i >= 0; i-- {
        num := nums[i]

        // 比较栈顶元素与当前num的大小
        for len(stack) > 0 && num >= nums[stack[len(stack)-1]] {
            // 弹出栈顶元素
            stack = stack[:len(stack)-1]
        }

        // 如果栈顶仍然有元素，说明栈顶对应的数字是比当前num大的下一个数字
        if len(stack) > 0 {
            ans[i] = (stack[len(stack)-1] - i) * (nums[stack[len(stack)-1]] - num)
        }

        // 将当前下标i压入栈中
        stack = append(stack, i)
    }

    // 输出结果，确保数字之间用空格分隔，且没有尾部空格
    for i := 0; i < n; i++ {
        if i > 0 {
            fmt.Print(" ")
        }
        fmt.Print(ans[i])
    }
    fmt.Println()
}

解法二：正序遍历

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 免费获取华为 OD 笔试真题题库和视频

# 输入表示n个操作的数组ops
ops = input().split(" ")

stack = list()      # 初始化一个空栈，在python中可以用list表示栈
isError = False     # 用于标记是否出现异常的标志，初始化为False表示没有异常

for record in ops:  # 遍历整个ops数组
    # 若record为数字，则直接将该数字加入栈中，注意要将str转为int
    if record != 'D' and record != 'C' and record != '+':
        stack.append(int(record))
    # 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
    elif record == 'D' and len(stack) >= 1:
        stack.append(stack[-1] * 2)
    # 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
    elif record == 'C' and len(stack) >= 1:
        stack.pop()
    # 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值
    elif record == '+' and len(stack) >= 2:
        stack.append(stack[-1] + stack[-2])
    # 如果不满足上述的任何条件，说明出现了异常，
    # 将isError修改为True，同时直接退出循环
    else:
        isError = True
        break

# 如果出现异常，输出-1
# 如果没有异常，输出整个栈中数字的总和
print(-1 if isError else sum(stack))


# 输入员工个数n
n = int(input())
# 输入N个员工的随机数数组
nums = list(map(int, input().split()))

# 构建一个单调栈，用来存放不同随机数的索引
# 栈中储存的索引所对应在height中的元素大小，从栈底至栈顶单调递减
# 即更大的数（的下标）位于栈底
stack = list()

# 构建列表ans，用来保存输出结果
# 初始化其中所有的元素和原数组一样，注意此处要使用拷贝
ans = nums.copy()

# 从头开始正序遍历nums中的每一个随机数
for i, num in enumerate(nums):
    # 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
    # 如果栈顶元素存在并且num【大于】栈顶元素stack[-1]这个下标对应的数字
    # 意味着nums中下标为stack[-1]的数字，找到了右边最近的比它更大的数字num
    while len(stack) > 0 and num > nums[stack[-1]]:
        # 首先获取栈顶元素的值，也就是要修改的位置
        preIndex = stack.pop()

        # i即为preIndex这个索引所对应的，下一个最近的更大的随机数的下标
        # 它们之间的下标距离为i-preIndex，数字大小差值为num-nums[preIndex]
        # 相乘后在ans中修改，作为答案
        ans[preIndex] = (i-preIndex)*(num-nums[preIndex])

    # 再把当前下标i储存入栈中
    # 注意：所储存的是下标i，而不是随机数num
    stack.append(i)

# ans中的int元素转成str后才能合并成字符串
print(" ".join(map(str, ans)))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入员工个数n
        int n = sc.nextInt();

        // 输入N个员工的随机数数组
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        // 构建一个单调栈，用来存放不同随机数的索引
        // 栈中储存的索引所对应的元素大小，从栈底至栈顶单调递减
        // 即更大的数（的下标）位于栈底
        Stack<Integer> stack = new Stack<>();

        // 构建列表ans，用来保存输出结果
        // 初始化其中所有的元素和原数组一样，注意此处要使用拷贝
        int[] ans = Arrays.copyOf(nums, n);

        // 从头开始正序遍历nums中的每一个随机数
        for (int i = 0; i < n; i++) {
            int num = nums[i];

            // 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
            // 如果栈顶元素存在并且num【大于】栈顶元素stack[-1]这个下标对应的数字
            // 意味着nums中下标为stack[-1]的数字，找到了右边最近的比它更大的数字num
            while (!stack.isEmpty() && num > nums[stack.peek()]) {
                // 首先获取栈顶元素的值，也就是要修改的位置
                int preIndex = stack.pop();

                // i即为preIndex这个索引所对应的，下一个最近的更大的随机数的下标
                // 它们之间的下标距离为i-preIndex，数字大小差值为num-nums[preIndex]
                // 相乘后在ans中修改，作为答案
                ans[preIndex] = (i - preIndex) * (num - nums[preIndex]);
            }

            // 再把当前下标i储存入栈中
            // 注意：所储存的是下标i，而不是随机数num
            stack.push(i);
        }

        // 输出结果，避免最后的空格
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                System.out.print(" ");  // 在输出之前先输出一个空格
            }
            System.out.print(ans[i]);
        }
        System.out.println();

        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n;
    // 输入员工个数n
    cin >> n;

    // 输入N个员工的随机数数组
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    // 构建一个单调栈，用来存放不同随机数的索引
    // 栈中储存的索引所对应的元素大小，从栈底至栈顶单调递减
    // 即更大的数（的下标）位于栈底
    stack<int> stk;

    // 构建列表ans，用来保存输出结果
    // 初始化其中所有的元素和原数组一样，注意此处要使用拷贝
    vector<int> ans = nums;

    // 从头开始正序遍历nums中的每一个随机数
    for (int i = 0; i < n; i++) {
        int num = nums[i];

        // 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
        // 如果栈顶元素存在并且num【大于】栈顶元素stack[-1]这个下标对应的数字
        // 意味着nums中下标为stack[-1]的数字，找到了右边最近的比它更大的数字num
        while (!stk.empty() && num > nums[stk.top()]) {
            // 首先获取栈顶元素的值，也就是要修改的位置
            int preIndex = stk.top();
            stk.pop();

            // i即为preIndex这个索引所对应的，下一个最近的更大的随机数的下标
            // 它们之间的下标距离为i-preIndex，数字大小差值为num-nums[preIndex]
            // 相乘后在ans中修改，作为答案
            ans[preIndex] = (i - preIndex) * (num - nums[preIndex]);
        }

        // 再把当前下标i储存入栈中
        // 注意：所储存的是下标i，而不是随机数num
        stk.push(i);
    }

    // 输出结果，避免最后的空格
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            cout << " ";  // 在输出之前先输出一个空格
        }
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// 定义最大员工数量
#define MAX_N 100000

int main() {
    int n;
    // 输入员工个数n
    scanf("%d", &n);

    // 输入N个员工的随机数数组
    int nums[MAX_N];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    // 构建一个单调栈，用来存放不同随机数的索引
    // 栈中储存的索引所对应在nums中的元素大小，从栈底至栈顶单调递减
    // 即更大的数（的下标）位于栈底
    int stack[MAX_N];
    int top = -1;  // 栈的顶端指针

    // 构建列表ans，用来保存输出结果
    // 初始化其中所有的元素和原数组一样，注意此处要使用拷贝
    int ans[MAX_N];
    for (int i = 0; i < n; i++) {
        ans[i] = nums[i];
    }

    // 逆序遍历nums中的每一个随机数
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];

        // 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
        // 如果栈顶元素存在并且num【大于等于】栈顶元素stack[-1]这个下标对应的数字
        // 说明栈顶元素stack[-1]这个下标对的数字，并不是随机数num右边最近的比num更大的元素
        // 需要将栈顶元素弹出，继续寻找比num大的栈顶元素
        while (top >= 0 && num >= nums[stack[top]]) {
            // 栈顶元素下标对应的数字不大于当前数字num，不是符合要求的更大数字，弹出
            top--;
        }

        // 完成弹出后，如果栈顶仍存在元素，说明stack[-1]所对应的数字，是严格比当前数字num大的下一个数字
        if (top >= 0) {
            // stack[top]即为i这个索引所对应的，下一个最近的更大的随机数的下标
            // 它们之间的下标距离为stack[top]-i，数字大小差值为nums[stack[top]]-num
            // 相乘后在ans中修改，作为答案
            ans[i] = (stack[top] - i) * (nums[stack[top]] - num);
        }

        // 再把当前下标i储存入栈中
        stack[++top] = i;
    }

    // 输出结果，避免最后的空格
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");  // 在输出之前先输出一个空格
        }
        printf("%d", ans[i]);
    }
    printf("\n");

    return 0;
}

Node JavaScript

const readline = require('readline');

// 创建 readline 接口
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

// 输入员工个数n
rl.question('', (n) => {
  // 输入N个员工的随机数数组
  rl.question('', (line) => {
    // 将输入的字符串转为数组
    let nums = line.split(' ').map(Number);

    // 构建一个单调栈，用来存放不同随机数的索引
    // 栈中储存的索引所对应在nums中的元素大小，从栈底至栈顶单调递减
    // 即更大的数（的下标）位于栈底
    let stack = [];

    // 构建列表ans，用来保存输出结果
    // 初始化其中所有的元素和原数组一样，注意此处要使用拷贝
    let ans = [...nums];

    // 从头开始正序遍历nums中的每一个随机数
    for (let i = 0; i < n; i++) {
      let num = nums[i];

      // 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
      // 如果栈顶元素存在并且num【大于】栈顶元素stack[-1]这个下标对应的数字
      // 意味着nums中下标为stack[-1]的数字，找到了右边最近的比它更大的数字num
      while (stack.length > 0 && num > nums[stack[stack.length - 1]]) {
        // 首先获取栈顶元素的值，也就是要修改的位置
        let preIndex = stack.pop();

        // i即为preIndex这个索引所对应的，下一个最近的更大的随机数的下标
        // 它们之间的下标距离为i-preIndex，数字大小差值为num-nums[preIndex]
        // 相乘后在ans中修改，作为答案
        ans[preIndex] = (i - preIndex) * (num - nums[preIndex]);
      }

      // 再把当前下标i储存入栈中
      // 注意：所储存的是下标i，而不是随机数num
      stack.push(i);
    }

    // ans中的int元素转成str后才能合并成字符串，避免最后的空格
    console.log(ans.join(' '));

    // 关闭 readline 接口
    rl.close();
  });
});

Go

package main

import "fmt"

func main() {
    var n int
    // 输入员工个数n
    fmt.Scan(&n)

    // 输入N个员工的随机数数组
    nums := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&nums[i])
    }

    // 构建一个单调栈，用来存放不同随机数的索引
    // 栈中储存的索引所对应在nums中的元素大小，从栈底至栈顶单调递减
    // 即更大的数（的下标）位于栈底
    stack := []int{}

    // 构建列表ans，用来保存输出结果
    // 初始化其中所有的元素和原数组一样，注意此处要使用拷贝
    ans := make([]int, n)
    copy(ans, nums)

    // 逆序遍历nums中的每一个随机数
    for i := n - 1; i >= 0; i-- {
        num := nums[i]

        // 第i个员工拿到的的随机数num，需要不断地与栈顶元素比较
        // 如果栈顶元素存在并且num【大于等于】栈顶元素stack[-1]这个下标对应的数字
        // 说明栈顶元素stack[-1]这个下标对的数字，并不是随机数num右边最近的比num更大的元素
        // 需要将栈顶元素弹出，继续寻找比num大的栈顶元素
        for len(stack) > 0 && num >= nums[stack[len(stack)-1]] {
            // 栈顶元素下标对应的数字不大于当前数字num，不是符合要求的更大数字，弹出
            stack = stack[:len(stack)-1]
        }

        // 完成弹出后，如果栈顶仍存在元素，说明stack[-1]所对应的数字，是严格比当前数字num大的下一个数字
        if len(stack) > 0 {
            // stack[len(stack)-1]即为i这个索引所对应的，下一个最近的更大的随机数的下标
            // 它们之间的下标距离为stack[len(stack)-1]-i，数字大小差值为nums[stack[len(stack)-1]]-num
            // 相乘后在ans中修改，作为答案
            ans[i] = (stack[len(stack)-1] - i) * (nums[stack[len(stack)-1]] - num)
        }

        // 再把当前下标i储存入栈中
        stack = append(stack, i)
    }

    // 输出结果，避免最后的空格
    for i, v := range ans {
        if i > 0 {
            fmt.Print(" ")
        }
        fmt.Print(v)
    }
    fmt.Println()
}

时空复杂度

时间复杂度：O(N)。无论是正序遍历还是逆序遍历，每个元素只会进出栈各至多一次。

空间复杂度：O(N)。单调栈所占空间。