本题为2024年9月19日华为-秋招机考原题

华为机考的介绍点击这里

题目内容

设计一个程序来处理特定的数组分析问题。

给定一个非负整数数组$arr$，其中每个整数用其十六进制表示中的数字之和来表示其“权重”(权重计算是基于十六进制表示中每位数字的和，$0$ ~ $9$代表权重$0$~ $9$，权重$A:10、B:11、C:12、D:13、E:14、F:15$)。

您的任务是找出数组中每个元素右侧第一个具有更大“权重”的元素，并返回一个新的数组，该数组包含这些元素的索引。

如果一个元素的右侧没有更大“权重”的元素，则对应位置返回 $-1$。

输入描述

第一行:一个整数 $N$，表示数组 $arr$ 的大小，$0<N<100000$

第二行:$N$ 个由空格分隔的非负整数，表示数组 $arr$，$0 ≤ arri ≤ 0xffffffff$

输出描述

一行:$N$个整数，表示每个元素右侧第一个权重更大的元素的索引，如果不存在则为$-1$。

样例1

输入

3
12 3 24

输出

-1 2 -1

说明

十六进制表示分别为:$[C,3,18]$

对应的权重分别为:$[12,3,1+8=9]$

对于第一个元素 $12$(权重$12$)，其右侧没有更大权重的元素，因此返回 $-1$

对于第二个元素 $3$(权重$3$)，其右侧第一个更大权重的元素是$24$(权重$9$)，位于索引$2$

对于第三个元素 $24$(权重$9$)，其不侧没有更大权重的元素，因此返回 $-1$。

样例2

输入

5
15 8 23 42 7

输出

-1 3 3 -1 -1

说明

十六进制表示分别为:$[F,8,17,2A,7]$。

对应的权重分别为:$[15,8,8,2+10=12,7]$。

对于第一个元素 $15$(权重$15$)，其右侧没有更大权重的元素，因此返回 $-1$。

对于第二个元素$8$(权重$8$)和第三个元素 $23$(权重$8$)，右侧第一个更大权重的元素是 $42$(权重$12$)，位于索引$3$。

对于第四个元素 $42$(权重$12$)和第五个元素$7$(权重$7$)，其右侧没有更大权重的元素，因此对应位置返回 $-1$。

单调栈讲解

通过之前几道栈基础题，我们可以总结一个规律： 对于每个元素，需要考虑它前面若干个数的影响时，可以使用栈来解决。

栈1：每一个右括号，需要寻找之前离它最近的左括号

栈2：每一个元素，需要寻找之前连续的两个相同元素

栈3：每一个数$x$，需要寻找之前连续若干个数的和等于$x$。

那么对于本题，我们需要寻找每个元素右侧第一个具有更大“权重”的元素 ，根据上述规律，自然的我们可以想到使用栈这种结构。让我们尝试“猜”一种本题可能的解法：

1.从右到左遍历元素，每一个元素$x$，连续让栈顶弹出，直到栈为空或者遇到一个数$y$，它大于$x$ 。 $y$ 就是第一个具有更大权重的元素。

2.把$x$装入栈中。

那么这就是单调栈，就这么简单

伪代码

arr : 权重数组
stack : 栈数组，开始为空 , 存数组下标
ans : 答案数组 
for i : n -> 1
	while stack is not empty and arr[i] >= arr[stack.top()]
    	stack.pop()
    if stack is not empty
	   	ans[i] = stack.top()
    else:
       	ans[i] = -1
    stack.push(i)
return ans

正确性说明

1.为什么小于$x$的栈顶元素都可以弹出栈？

对于一个元素$x$ ， 如果它右侧存在一个数$y$ , 使得$y < x$ ， 那么对于未来要考虑的元素(也就是$x$左侧的元素)来说，$y$ 不可能是答案，因为$x$ 既比$y$ 大 又 比 $y$ 更接近未来要考虑的元素。所以我们需要不停的把小于$x$的元素弹出栈。

2.为什么叫单调栈？

对于每一个元素来说，连续弹出的操作会让栈顶元素$y > x$ 。所以栈总体是呈现递减的趋势。

3.时间复杂度是多少？

$O(n)$ , 因为对于每个元素，它最多入栈一次，出栈一次。所以操作次数最多为$2n$ 。

本题思路

计算每个元素的“权重”（基于其十六进制表示中各位数字的和），然后找出每个元素右侧第一个具有更大“权重”的元素的索引。如果不存在，则返回 -1。

使用单调栈从右向左遍历数组，计算每个元素的权重并记录其右侧第一个更大权重元素的索引，不存在则为-1。

1.权重计算

权重的计算基于十六进制的表示，十六进制数字0-9的权重分别为0-9，而A-F的权重分别为10-15。我们可以通过位运算高效地计算权重。具体而言，利用位运算获取每个数字的值并累加起来。

2.单调栈步骤

1. 从右到左遍历数组。
2. 使用栈来存储元素的索引，保持栈内元素的权重递减的特性。
3. 遍历过程中，对于当前元素，弹出所有权重小于或等于当前元素的索引，这样栈顶的元素就是右侧第一个更大权重的元素。
4. 如果栈为空，说明右侧没有更大权重的元素，返回-1；否则返回栈顶元素的索引。

Python代码

def compute_weight(n):
    """计算整数 n 的十六进制表示中各位数字的和"""
    if n == 0:
        return 0
    s = 0
    while n > 0:
        digit = n & 0xF  # 获取最低四位，即一个十六进制数字
        s += digit
        n >>= 4  # 右移四位，处理下一个十六进制数字
    return s

def main():
    import sys
    # 读取第一个输入，数组的大小 N
    N = int(input())
    
    # 读取第二行的 N 个整数
    arr = list(map(int, input().split()))
    
    # 计算每个元素的权重
    weights = [compute_weight(num) for num in arr]
    
    # 初始化答案数组，默认所有位置为 -1
    answer = [-1] * N
    
    stack = []  # 栈中存储的是元素的索引
    
    # 从右到左遍历数组
    for i in range(N-1, -1, -1):
        # 弹出栈中所有权重小于或等于当前元素权重的元素
        while stack and weights[stack[-1]] <= weights[i]:
            stack.pop()
        # 如果栈不为空，栈顶元素就是右侧第一个权重更大的元素
        if stack:
            answer[i] = stack[-1]
        else:
            answer[i] = -1
        # 将当前元素的索引压入栈中
        stack.append(i)
    
    # 输出结果，以空格分隔
    print(' '.join(map(str, answer)))

if __name__ == "__main__":
    main()