2026 华为OD机试真题 4月26日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

给定一个整数数组 $portRates$，$portRates[i]$ 表示该端口第 $i$ 分钟端口流量速率（单位:$bps$）。

输入描述

给定一个整数数组 $portRates$，$portRates[i]$ 表示该端口第 $i$ 分钟端口流量速率（单位:$bps$）。

输出描述

返回一个数组 ratesStatratesStat，ratesStat[i]ratesStat[i] 表示多少分钟以后出现比当前更大的流量速率，如果没有出现更大的流量速率，则值为0。

示例1

输入

730,740,750,710,690,720,760,730

输出

1,1,4,2,1,1,0,0

说明

输入数组第 0分钟端口流速是 730bps，第 1 分钟端口流速是 740bps，相差 1 分钟，则返回数组第 0 个元素的值为 1；

输入数组第 2 分钟端口流速是 750 bps，第 6 分钟端口流速是 760 bps，相差 4 分钟，则返回数组第 2 个元素的值为 4。

示例2

输入

800

输出

说明

只有一个数据，返回 0

示例3

输入

800,700

输出

0,0

说明

只有两个元素，后一个流量比第一个流量低，返回 [0,0]

示例4

输入

700,800

输出

1,0

说明

只有两个元素，后一个流量比第一个流量高，返回 [1,0]

解题思路

核心思想

这道题本质上是经典的“下一个更大元素”（Next Greater Element）问题，可以通过单调栈（Monotonic Stack）来高效求解。 题目要求对于数组中的每一个元素，找到其之后第一个比它大的元素，并计算它们之间的索引差值。如果之后没有更大的元素，则返回 。

单调栈的思路如下：

1. 维护一个单调递减的栈，栈中存储元素的索引。
2. 从左到右遍历数组，对于当前遍历到的元素 rates[i]：
   • 如果栈不为空，且 rates[i] 大于栈顶索引对应的元素 rates[stack.peek()]，说明找到了栈顶元素的下一个更大元素。
   • 弹出栈顶索引 idx，此时 idx 的下一个更大元素就是 rates[i]，它们之间的距离就是 i - idx。将结果数组 ans[idx] 更新为 i - idx。
   • 循环执行上述出栈操作，直到栈为空或当前元素不再大于栈顶元素。
3. 将当前元素的索引 i 压入栈中。
4. 遍历结束后，栈中剩余的索引表示没有找到更大的元素，其对应的结果应为 （初始化时默认为 即可）。

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。虽然有一个嵌套的 while 循环，但每个元素最多入栈一次，出栈一次，所以总的操作次数是 $2N$，时间复杂度为 $O(N)$。
• 空间复杂度：$O(N)$。在最坏情况下（例如数组是单调递减的），所有元素的索引都会压入栈中，因此栈的最大空间为 $O(N)$。结果数组也需要 $O(N)$ 的空间。