【华为面试题】单调栈

川长思鸟来 2024-03-23 22:10 11阅读 0赞

### 题目 ###

为答谢员工的付出，公司决定通过一个小游戏为每位员工分发奖金。每位员工会抽取一个随机数。员工按照工号顺序排列。每名员工的奖金计算如下：找到他后面的第一位数字比他大的员工，奖金为“两者的数字差 × 两者间的员工数”。若没有找到，则他获得他所抽取的随机数作为奖金。

例如，员工的随机数字为：2, 10, 3。那么第一个员工的奖金是 (10 - 2) × 1 = 8，第二个员工的奖金是10（因为后面没有更大的数字），第三个员工的奖金是3。

输入描述：

第一行为一个整数，表示员工的数量 n（1 ≤ n ≤ 10000）。  
第二行为 n 个整数，代表每位员工抽取的随机数字，数字范围为1到100000，且不重复。  
输出描述：

输出 n 个整数，表示每位员工的奖金，数值间用空格分隔。

输入：  
3  
2 10 3

输出：  
8 10 3

### 代码 ###

/**
     * 计算每位员工的奖金
     * @param {number} N - 员工的数量
     * @param {number[]} nums - 员工抽取的随机数字列表
     * @return {number[]} - 每位员工的奖金
     */
    function calculateBonus(N, nums) {
        
        // 对于每个员工，找出其后面第一个数字比它大的员工的差值和距离
        let res = findMax(nums);
        let result = [];
        for (let i = 0; i < N; i++) {
        
            // 如果后面没有数字比它大，则其奖金为自己抽取的数字
            if (res[i] === -1) {
        
                result.push(nums[i]);
            } else {
        
                // 否则奖金为两者的数字差 × 两者间的员工数
                result.push(res[i]);
            }
        }
        return result;
    }
    
    /**
     * 使用单调栈找到每个员工后面的第一个数字比他大的员工
     * @param {number[]} array - 员工抽取的随机数字列表
     * @return {number[]} - 每位员工后面比他大的第一个员工的差值和距离
     */
    function findMax(array) {
        
        let len = array.length;
        // st 用于存储数组中的下标，它们代表的值在当前位置都还没有找到比自己大的数
        let st = [];
        let res = new Array(len).fill(0);
        let i = 0;
        // 遍历数组
        while (i < len) {
        
            // 如果单调栈为空，或者当前数字小于或等于栈顶数字
            if (st.length === 0 || array[i] <= array[st[st.length - 1]]) {
        
                // 当前下标入栈
                st.push(i);
                i++;
            } else {
        
                // 找到了比栈顶数字大的数
                let top = st.pop();
                res[top] = (array[i] - array[top]) * (i - top);
            }
        }
        // 清空栈，并将结果设为-1，表示没有找到比它大的数
        while (st.length !== 0) {
        
            res[st.pop()] = -1;
        }
        return res;
    }
    
    // 测试用例
    let N = 3;
    let nums = [2, 10, 3];
    console.log(calculateBonus(N, nums).join(" "));