题面解释:

题目要求设计一个程序来处理一个非负整数数组的分析。给定数组中的每个整数，我们需要计算其在十六进制表示中的“权重”，即每个数字之和（0-9代表其权重为0-9，A-F分别代表权重10-15）。然后，对于数组中每个元素，我们要找到其右侧第一个权重更大的元素，并返回该元素的索引。如果没有这样的元素，返回-1。

类似的题目:

LeetCode 496. 下一个更大元素 I

思路:单调栈

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

我们可以使用单调栈来高效地解决这个问题。使用单调栈从右向左遍历数组，计算每个元素的权重并记录其右侧第一个更大权重元素的索引，不存在则为-1。

题解

我们需要解决的问题是，给定一个非负整数数组，我们需要计算每个元素在十六进制表示中的“权重”，即所有数字之和。接着，找出每个元素右侧第一个具有更大“权重”的元素的索引。如果没有这样的元素，返回-1。

权重计算

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

使用单调栈的思路

为了找到每个元素右侧第一个权重更大的元素，我们可以使用单调栈的策略：

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

这种方法的时间复杂度为O(N)，因为每个元素最多被入栈和出栈一次，非常高效。

代码

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()))
    
    # 确保读取的数组长度与 N 一致
    if len(arr) != N:
        print("输入的数组长度与指定的 N 不一致。")
        return
    
    # 计算每个元素的权重
    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()

cpp

#include <bits/stdc++.h>
using namespace std;

// 函数用于计算整数 n 的十六进制表示中各位数字的和
int compute_weight(unsigned int n) {
    if (n == 0) return 0; // 如果 n 为 0，权重为 0
    int sum = 0; // 初始化权重和
    while (n > 0) {
        sum += (n & 0xF); // 获取最低四位（十六进制的最后一位）
        n >>= 4;          // 右移四位，处理下一个十六进制位
    }
    return sum; // 返回计算得到的权重
}

int main(){
    ios::sync_with_stdio(false); // 提高输入输出效率
    cin.tie(0); // 解除 cin 和 cout 的绑定，进一步提高效率
    
    int N;
    cin >> N; // 读取数组大小
    vector<unsigned int> arr(N); // 初始化数组
    for(int i = 0; i < N; ++i){
        cin >> arr[i]; // 读取数组元素
    }
    
    // 计算每个元素的权重
    vector<int> weights(N);
    for(int i = 0; i < N; ++i){
        weights[i] = compute_weight(arr[i]); // 计算并存储权重
    }
    
    // 初始化答案数组，默认所有位置为 -1
    vector<int> answer(N, -1);
    // 使用栈存储索引
    stack<int> st;
    
    // 从右到左遍历
    for(int i = N - 1; i >= 0; --i){
        // 弹出栈中所有权重小于或等于当前元素的索引
        while(!st.empty() && weights[st.top()] <= weights[i]){
            st.pop(); // 弹出不满足条件的元素
        }
        // 如果栈不为空，栈顶元素就是右侧第一个更大权重的元素
        if(!st.empty()){
            answer[i] = st.top(); // 记录结果
        }
        // 将当前元素的索引压入栈中
        st.push(i);
    }
    
    // 输出结果
    for(int i = 0; i < N; ++i){
        if(i > 0) cout << ' '; // 在输出前加空格
        cout << answer[i]; // 输出结果
    }
    cout << '\n'; // 输出换行符
    
    return 0; // 程序结束
}

java

import java.io.*;
import java.util.*;

public class Main {
    // 函数用于计算整数 n 的十六进制表示中各位数字的和
    public static int computeWeight(long n){
        if(n == 0) return 0;
        int sum = 0;
        while(n > 0){
            sum += (n & 0xF);
            n >>=4;
        }
        return sum;
    }
    
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 和 BufferedWriter 提高输入输出效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        // 读取第一个输入，数组的大小 N
        int N = Integer.parseInt(br.readLine());
        
        // 读取第二行的 N 个整数
        st = new StringTokenizer(br.readLine());
        long[] arr = new long[N];
        for(int i=0; i<N; i++){
            arr[i] = Long.parseUnsignedLong(st.nextToken());
        }
        
        // 计算每个元素的权重
        int[] weights = new int[N];
        for(int i=0; i<N; i++){
            weights[i] = computeWeight(arr[i]);
        }
        
        // 初始化答案数组，默认所有位置为 -1
        int[] answer = new int[N];
        Arrays.fill(answer, -1);
        
        // 使用栈存储索引
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 从右到左遍历数组
        for(int i=N-1; i>=0; i--){
            // 弹出栈中所有权重小于或等于当前元素的索引
            while(!stack.isEmpty() && weights[stack.peek()] <= weights[i]){
                stack.pop();
            }
            // 如果栈不为空，栈顶元素就是右侧第一个更大权重的元素
            if(!stack.isEmpty()){
                answer[i] = stack.peek();
            }
            // 将当前元素的索引压入栈中
            stack.push(i);
        }
        
        // 构建输出结果
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            sb.append(answer[i]);
            if(i != N-1){
                sb.append(' ');
            }
        }
        sb.append('\n');
        bw.write(sb.toString());
        bw.flush();
    }
}

题目内容

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

给定一个非负整数数组$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$。