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

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

题目描述

春节将至，工人要在古镇老街挂灯笼。街上有 N 个挂灯点，每个点因建筑结构不同，工人挂上的灯笼的尺寸M也不同（数值越大表示灯笼越大）。

工人认为美观的灯笼必须按非递增尺寸顺序挂置，即后续灯笼尺寸不能超过当前灯笼（只能相同或更小）。

工人完成灯笼挂接后，需要你代替他判断：

1、这排灯笼里，满足美观定义的最长连续灯笼区域有多少个灯笼；

2、这段最长连续区域是从哪个挂灯点开始？（当存在多个最长连续区域时选择最左边的挂灯点）

输入描述

N 个正整数 M（1≤M≤100），表示每个挂灯点所挂的灯笼尺寸。

输出描述

输出两个整数：第一个是符合题意的灯笼数，第二个是开始挂灯笼的挂灯点位置（从 0 开始计数）。

示例1

输入

[5,3,4,4,2,1]

输出

[4,2]

说明

灯笼尺寸序列为 [5,3,4,4,2,1]。存在长度为4的非递增连续子序列：[4,4,2,1]（位置 2−5）。

示例2

输入

[5,4,3,2,1]

输出

[5,0]

说明

灯笼尺寸序列为 [5,4,3,2,1]。整个序列满足非递增要求，长度为 5，起始位置为 0。

示例3

输入

[2,2,2,2]

输出

[4,0]

说明

灯笼尺寸序列为 [2,2,2,2]。所有灯笼尺寸相等，满足非递增要求，长度为 4，起始位置为 0。

解题思路

本题要求在一个整数数组中寻找“最长连续非递增子序列”。 具体来说，我们需要找到一个连续的区域，使得区域内的灯笼尺寸满足 $Mi \ge M{i+1}$，并输出该区域的长度和起始位置。如果存在多个长度相同的最长区域，返回最左侧的那个（即起始位置索引最小的）。

我们可以使用一次线性遍历来解决这个问题：

1. 状态初始化：

   • 使用 best_len 记录全局最长非递增区域的长度，初始为 1（即使只有一个灯笼，长度也是 1）。
   • 使用 best_start 记录全局最长非递增区域的起始位置，初始为 0。
   • 使用 cur_len 记录当前正在考察的非递增区域的长度，初始为 1。
   • 使用 cur_start 记录当前正在考察的非递增区域的起始位置，初始为 0。

2. 线性遍历：

   • 从第二个灯笼（索引 $i = 1$）开始遍历数组。
   • 如果当前灯笼的尺寸小于等于前一个灯笼（nums[i] <= nums[i - 1]），说明满足非递增要求，当前连续区域长度 cur_len 增加 1。
   • 否则，说明非递增区域在这里断开，我们需要重新开始计算一个新的区域：将 cur_len 重置为 1，并将 cur_start 更新为当前索引 $i$。

3. 结果更新：

   • 在每次迭代的最后，检查 cur_len 是否严格大于 best_len。
   • 如果是，则更新 best_len = cur_len，同时更新 best_start = cur_start。
   • 必须使用“严格大于”（>），这样在遇到长度相同的连续区域时，就不会覆盖之前找到的最左侧的结果，完美契合题目“存在多个最长连续区域时选择最左边的挂灯点”的要求。

复杂度分析

• 时间复杂度：$O(N)$。我们只需要对长度为 $N$ 的数组进行一次从头到尾的线性扫描即可得到结果。
• 空间复杂度：$O(1)$。只使用了几个常数级别的变量来记录长度和起始位置，不需要额外的存储空间（不计算存储输入数组本身的空间）。