单调栈讲解

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

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

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

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

本题为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$。