一、问题描述

题目描述

A 公司准备对其下面的 N 个产品评选最差奖。评选的方式是首先对每个产品进行评分，然后根据评分区间计算相邻几个产品中最差的产品。评选的标准是依次找到从当前产品开始前 M 个产品中最差的产品，请给出最差产品的评分序列。

输入描述

• 第一行，数字 M，表示评分区间的长度，取值范围是 0 < M < 10000。
• 第二行，产品的评分序列，比如 [12,3,8,6,5]，产品数量 N 范围是 -10000 < N < 10000。

输出描述

输出评分区间内最差产品的评分序列。

用例

输入

3
12,3,8,6,5

输出

3,3,5

说明

• 12,3,8 最差的是 3。
• 3,8,6 最差的是 3。
• 8,6,5 最差的是 5。

题目解析

问题理解

题目要求我们从产品的评分序列中，依次找到每个长度为 M 的滑动窗口中的最小值（即最差产品的评分），并输出这些最小值的序列。

关键点

1. 滑动窗口：窗口长度为 M，依次滑动计算每个窗口的最小值。
2. 最差产品：每个窗口中的最小值即为最差产品的评分。
3. 输出结果：输出所有窗口的最小值序列。

解题思路

暴力解法

1. 遍历滑动窗口：从第一个产品开始，依次滑动窗口，窗口长度为 M。
2. 计算窗口最小值：对于每个窗口，遍历窗口内的所有产品，找到最小值。
3. 输出结果：将所有窗口的最小值按顺序输出。

时间复杂度

• 暴力解法的时间复杂度为 O((N - M + 1) * M)，其中 N 是产品数量，M 是窗口长度。

优化思路

如果需要优化时间复杂度，可以使用单调队列（Monotonic Queue）或堆（Heap）等数据结构，将时间复杂度优化到 O(N)。

结论

通过滑动窗口遍历评分序列，并计算每个窗口的最小值，我们可以得到最差产品的评分序列。最终输出结果为所有窗口的最小值序列。

最终答案

输出评分区间内最差产品的评分序列。例如：

3,3,5

二、JavaScript算法源码

这段JavaScript代码实现了一个在ACM模式下从控制台读取输入的程序。它通过readline模块实现连续行读取，并针对给定大小的滑动窗口计算数组中每个窗口的最小值。以下是对代码的详细讲解和注释。

代码解析

1. 准备读取输入

javascript">const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];

• 使用readline模块创建接口rl，用于处理标准输入输出。
• 定义一个数组lines，用于存储每行输入。

2. 读取输入

javascript">rl.on("line", (line) => {lines.push(line);if (lines.length === 2) {const m = lines[0] - 0;const arr = lines[1].split(",").map(Number);console.log(getResult(arr, m));lines.length = 0;}
});

• rl.on("line", (line) => {...})：设置一个事件监听器，当有新行输入时执行回调函数。
• lines.push(line)：将输入的每行数据存储到lines数组中。
• 当lines数组长度为2时，意味着已经读取到了两行输入：
  • const m = lines[0] - 0;：将第一行转换为数字，表示滑动窗口的大小m。
  • const arr = lines[1].split(",").map(Number);：将第二行以,分割并转换为数字数组arr。
  • 调用getResult(arr, m)函数计算结果并输出。
  • 重置lines数组，准备接收下一组输入。

3. 计算滑动窗口最小值

javascript">function getResult(arr, m) {const ans = [];for (let i = 0; i <= arr.length - m; i++) {ans.push(Math.min(...arr.slice(i, i + m)));}return ans.join(",");
}

• function getResult(arr, m)：定义一个函数，接受输入数组arr和滑动窗口大小m。
• 初始化结果数组ans。
• 遍历数组，for (let i = 0; i <= arr.length - m; i++)：
  • arr.slice(i, i + m)：截取从索引i开始，长度为m的子数组。
  • Math.min(...arr.slice(i, i + m))：求子数组的最小值。
  • 将最小值添加到ans数组中。
• 返回结果数组ans，并用,连接成字符串。

---

示例运行

假设输入如下：

3
1,3,5,2,8,6

解释：

1. 输入行1：3（滑动窗口大小m）。
2. 输入行2：1,3,5,2,8,6（输入数组）。

计算过程：

• 窗口1：[1, 3, 5]，最小值为1。
• 窗口2：[3, 5, 2]，最小值为2。
• 窗口3：[5, 2, 8]，最小值为2。
• 窗口4：[2, 8, 6]，最小值为2。

输出：

1,2,2,2

代码总结

• 这段代码有效地实现了滑动窗口的最小值计算，适用于ACM比赛模式的输入处理。
• 使用readline模块处理标准输入，使其适合多行输入的场景。
• 代码逻辑简洁清晰，可适应不同大小的滑动窗口和数组。

这段JavaScript代码实现了一个滑动窗口最小值计算的功能，使用的是数组模拟的单调队列。通过单调队列的方式，我们能够在每个滑动窗口内高效地计算最小值。接下来，我将详细解释代码的功能和实现方式。

代码解析

1. 输入处理

javascript">const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
rl.on("line", (line) => {lines.push(line);if (lines.length === 2) {const m = lines[0] - 0;const arr = lines[1].split(",").map(Number);console.log(getResult(arr, m));lines.length = 0;}
});

• readline模块：用于处理控制台输入。
• rl.on("line", ...)：监听输入的每一行，并将其存储到lines数组中。
  • 当lines数组长度为2时，说明已经读取了窗口大小m和数组arr。
  • const m = lines[0] - 0;：将字符串形式的整数转换为数字。
  • const arr = lines[1].split(",").map(Number);：将逗号分隔的字符串转换为数字数组。
• 调用getResult(arr, m)函数并输出结果。

2. 滑动窗口最小值算法

javascript">function getResult(nums, k) {const queue = [];  // 用于存储当前滑动窗口的候选最小值const ans = [];    // 用于存储每个窗口的最小值// 初始化第一个窗口的队列for (let i = 0; i < k; i++) {while (queue.length && queue.at(-1) > nums[i]) {queue.pop();}queue.push(nums[i]);}ans.push(queue[0]); // 将第一个窗口的最小值加入结果集// 处理后续窗口for (let i = k; i < nums.length; i++) {if (nums[i - k] == queue[0]) {queue.shift(); // 移出窗口外的元素}// 保持队列单调性while (queue.length && queue.at(-1) > nums[i]) {queue.pop();}queue.push(nums[i]);ans.push(queue[0]); // 当前窗口的最小值}return ans.join(); // 返回结果，以逗号分隔
}

• 队列的使用：queue用于模拟双端队列以维护当前窗口的最小值。

• 初始化第一个窗口：

  • 遍历第一个窗口的元素，维护一个单调递增队列。
  • while (queue.length && queue.at(-1) > nums[i]) queue.pop();：确保当前元素比队尾元素小，维持单调性。
  • queue.push(nums[i]);：将当前元素加入队列。
  • ans.push(queue[0]);：第一个窗口的最小值即为队首元素。

• 处理后续窗口：

  • if (nums[i - k] == queue[0]) queue.shift();：如果滑出窗口的元素是最小值，则将其从队列移除。
  • 使用同样的方法更新队列，保持单调性。
  • 将当前的最小值（队首元素）加入结果。

代码总结

• 效率：通过使用单调队列，算法能够在O(n)的时间复杂度内完成最小值计算，比简单遍历更加高效。
• 灵活性：该实现可处理任意长度的输入数组和窗口大小。
• 适用性：适合在Node.js环境下运行，处理标准输入输出。

示例

假设输入如下：

3
1,3,5,2,8,6

计算过程：

• 窗口1：[1, 3, 5]，最小值为1。
• 窗口2：[3, 5, 2]，最小值为2。
• 窗口3：[5, 2, 8]，最小值为2。
• 窗口4：[2, 8, 6]，最小值为2。

输出：

1,2,2,2

这段代码高效地实现了滑动窗口最小值的计算。通过使用数组模拟的单调队列，它能够在更低的时间复杂度内解决问题。

三、Java算法源码

这段Java代码实现了一个功能：根据用户输入的数组和窗口大小，计算数组中每个滑动窗口的最小值，并将结果以逗号分隔的字符串形式输出。下面是对代码的详细解释和注释。

代码解析

1. 主函数 main

java">public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();Integer[] arr =Arrays.stream(sc.next().split(",")).map(Integer::parseInt).toArray(Integer[]::new);System.out.println(getResult(arr, m));
}

• Scanner：用于从标准输入中读取数据。

  • int m = sc.nextInt();：读取一个整数，表示滑动窗口的大小m。

• 数组输入：

  • sc.next().split(",")：读取下一个输入行并用逗号分隔，得到字符串数组。
  • Arrays.stream(...).map(Integer::parseInt).toArray(Integer[]::new)：将字符串数组转换为Integer数组。
    • Arrays.stream(...)：创建一个流。
    • .map(Integer::parseInt)：将每个字符串转换为整数。
    • .toArray(Integer[]::new)：将流转换为Integer数组。

• 获取结果并输出：

  • 调用getResult(arr, m)计算结果。
  • System.out.println(...)：输出结果字符串。

2. 函数 getResult

java">public static String getResult(Integer[] arr, int m) {ArrayList<Integer> ans = new ArrayList<>();for (int i = 0; i <= arr.length - m; i++) {int min = Integer.MAX_VALUE;for (int j = i; j < i + m; j++) min = Math.min(min, arr[j]);ans.add(min);}StringJoiner sj = new StringJoiner(",");for (Integer an : ans) {sj.add(an + "");}return sj.toString();
}

• 滑动窗口最小值计算：

  • 初始化结果列表ans来存储每个窗口的最小值。
  • 遍历数组：
    • 外循环for (int i = 0; i <= arr.length - m; i++)：定位每个滑动窗口的起始位置。
    • 初始化min为最大整数值Integer.MAX_VALUE。
    • 内循环for (int j = i; j < i + m; j++)：遍历当前窗口的每个元素。
    • min = Math.min(min, arr[j]);：更新窗口最小值。
    • 将当前窗口的最小值添加到ans列表中。

• 结果输出格式化：

  • 使用StringJoiner将ans列表中的元素连接成字符串，使用逗号分隔。
  • 遍历ans列表，将每个元素添加到StringJoiner对象sj中。
  • 返回结果字符串。

示例运行

假设输入如下：

3
1,3,5,2,8,6

解释：

1. 输入行1：3（滑动窗口大小m）。
2. 输入行2：1,3,5,2,8,6（输入数组）。

计算过程：

• 窗口1：[1, 3, 5]，最小值为1。
• 窗口2：[3, 5, 2]，最小值为2。
• 窗口3：[5, 2, 8]，最小值为2。
• 窗口4：[2, 8, 6]，最小值为2。

输出：

1,2,2,2

代码总结

• 灵活性：代码灵活地读取用户输入并处理滑动窗口计算。
• 效率：通过简单的嵌套循环实现计算，适合小到中等规模的数据处理。
• 易于理解：代码结构清晰，易于理解和维护，适合初学者学习滑动窗口技术。

四、Python算法源码

这段Python代码实现了一个功能：根据用户输入的数组和窗口大小，计算数组中每个滑动窗口的最小值，并将结果以逗号分隔的字符串形式输出。以下是对代码的详细解释和注释。

代码解析

1. 读取输入

python">m = int(input())
arr = list(map(int, input().split(",")))

• m = int(input())：读取一个整数输入，表示滑动窗口的大小m。
• arr = list(map(int, input().split(",")))：
  • input().split(",")：读取一行输入并用逗号分隔，生成一个字符串列表。
  • map(int, ...)：将字符串列表的每个元素转换为整数。
  • list(...)：将转换后的结果存储为一个列表arr。

2. 定义算法函数 getResult

python">def getResult(arr, m):ans = []for i in range(0, len(arr) - m + 1):ans.append(min(arr[i:i+m]))return ",".join(map(str, ans))

• 初始化结果列表ans，用于存储每个滑动窗口的最小值。

• 遍历数组：

  • for i in range(0, len(arr) - m + 1)：循环遍历每个滑动窗口的起始位置i。
  • arr[i:i+m]：使用切片获取当前窗口的子数组。
  • min(arr[i:i+m])：计算当前窗口的最小值。
  • ans.append(...)：将当前窗口的最小值添加到结果列表ans中。

• 结果格式化输出：

  • ",".join(map(str, ans))：将ans列表中的整数转换为字符串，并用逗号连接成一个字符串。

3. 调用算法并输出结果

python">print(getResult(arr, m))

• 调用getResult(arr, m)函数来计算滑动窗口的最小值。
• 使用print函数输出结果字符串。

示例运行

假设输入如下：

3
1,3,5,2,8,6

解释：

1. 输入行1：3（滑动窗口大小m）。
2. 输入行2：1,3,5,2,8,6（输入数组）。

计算过程：

• 窗口1：[1, 3, 5]，最小值为1。
• 窗口2：[3, 5, 2]，最小值为2。
• 窗口3：[5, 2, 8]，最小值为2。
• 窗口4：[2, 8, 6]，最小值为2。

输出：

1,2,2,2

代码总结

• 简洁性：代码使用Python的强大内置函数（如min、map、join），实现简洁高效。
• 可读性：通过直观的切片和列表操作，代码容易理解。
• 适用性：适合处理小到中等规模的数组滑动窗口问题。对于较大数据集或更复杂的窗口操作，可能需要优化或使用高级数据结构。

五、C/C++算法源码：

以下是将上述Java代码分别改为C++和C的实现，并附上中文详细注释和代码的讲解。

---

C++ 实现

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <climits>using namespace std;// 滑动窗口最小值计算函数
string getResult(const vector<int>& arr, int m) {vector<int> ans;// 遍历数组，计算每个滑动窗口的最小值for (size_t i = 0; i <= arr.size() - m; i++) {int minVal = INT_MAX; // 初始化最小值为最大整数for (size_t j = i; j < i + m; j++) {minVal = min(minVal, arr[j]); // 更新当前窗口的最小值}ans.push_back(minVal); // 保存当前窗口最小值}// 将结果转化为逗号分隔的字符串stringstream result;for (size_t i = 0; i < ans.size(); i++) {result << ans[i];if (i != ans.size() - 1) {result << ","; // 添加逗号分隔符}}return result.str();
}int main() {int m;string input;// 输入窗口大小mcin >> m;cin.ignore(); // 忽略换行符// 输入数组，逗号分隔getline(cin, input);stringstream ss(input);vector<int> arr;string temp;// 将字符串解析为整数数组while (getline(ss, temp, ',')) {arr.push_back(stoi(temp));}// 调用getResult函数并输出结果cout << getResult(arr, m) << endl;return 0;
}

---

C++ 实现讲解

1. 输入处理：

   • 首先读取滑动窗口大小m，然后通过getline()函数读取整行输入数组。
   • 使用stringstream和getline()函数将逗号分隔的字符串解析成整数数组。

2. 滑动窗口最小值计算：

   • 遍历数组的每个滑动窗口起始位置i，从i到i + m计算当前窗口的最小值。
   • 使用std::min函数更新窗口中的最小值，并将其存储到结果数组ans中。

3. 结果格式化：

   • 将结果数组ans中的元素拼接成逗号分隔的字符串，使用stringstream完成拼接。

4. 输出结果：

   • 调用getResult函数，输出滑动窗口的最小值结果。

---

C 实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>// 计算滑动窗口的最小值函数
void getResult(int* arr, int n, int m, char* result) {char buffer[10];int idx = 0;// 遍历每个滑动窗口for (int i = 0; i <= n - m; i++) {int minVal = INT_MAX; // 初始化当前窗口的最小值for (int j = i; j < i + m; j++) {if (arr[j] < minVal) {minVal = arr[j]; // 更新窗口的最小值}}// 将最小值转换为字符串并拼接到结果中sprintf(buffer, "%d", minVal);strcpy(result + idx, buffer);idx += strlen(buffer);// 添加逗号分隔符（除最后一个值外）if (i != n - m) {result[idx++] = ',';}}result[idx] = '\0'; // 添加字符串结束符
}int main() {int m;char input[1000];int arr[1000];int n = 0;// 输入滑动窗口大小scanf("%d", &m);getchar(); // 清除缓冲区的换行符// 输入数组（逗号分隔）fgets(input, sizeof(input), stdin);char* token = strtok(input, ",");while (token != NULL) {arr[n++] = atoi(token);token = strtok(NULL, ",");}// 计算滑动窗口的最小值并输出结果char result[1000];getResult(arr, n, m, result);printf("%s\n", result);return 0;
}

---

C 实现讲解

1. 输入处理：

   • 使用scanf读取滑动窗口大小m。
   • 使用fgets读取整行输入，并用strtok按逗号分隔解析为整数数组。

2. 滑动窗口最小值计算：

   • 遍历数组的每个滑动窗口起始位置i，从i到i + m计算当前窗口的最小值。
   • 在内循环中比较，并更新当前窗口的最小值。

3. 结果格式化：

   • 使用sprintf将整数值转换为字符串，并拼接到结果字符串中。
   • 添加逗号分隔符，但确保最后一个元素不添加逗号。

4. 输出结果：

   • 调用getResult函数，结果存储在字符串result中，最后使用printf输出。

---

示例输入与输出

输入：

3
1,3,5,2,8,6

输出：

1,2,2,2

---

两种实现的对比

特性	C++ 实现	C 实现
语言特性	使用STL（如vector、string等），代码简洁	仅使用C标准库，代码稍显复杂
字符串处理	使用stringstream处理字符串拼接	使用strtok和sprintf处理字符串
易读性	更高，贴近自然语言	较低，需手动管理字符串拼接和数组
适用场景	适合C++环境和更复杂的数据处理	适合C语言环境的简洁实现

两种实现均可正确完成滑动窗口最小值的计算，开发者可以根据具体需求选择适合的语言和实现方式。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

1. 机试是进入技术面的第一关：
   华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

2. 技术面试需要手撕代码：
   技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

3. 入职后的可信考试：
   入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

   • 入门级：主要考察基础算法与编程能力。
   • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
   • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

1. 关注历年真题：

   • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
   • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

2. 适应新题目：

   • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
   • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

3. 掌握常见算法：
   华为OD考试通常涉及以下算法和数据结构：

   • 排序算法（快速排序、归并排序等）
   • 动态规划（背包问题、最长公共子序列等）
   • 贪心算法
   • 栈、队列、链表的操作
   • 图论（最短路径、最小生成树等）
   • 滑动窗口、双指针算法

4. 保持编程规范：

   • 注重代码的可读性和注释的清晰度。
   • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

1. 官方参考：

   • 华为招聘官网或相关的招聘平台会有一些参考信息。
   • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

2. 加入刷题社区：

   • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
   • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

3. 寻找系统性的教程：

   • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
   • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

1. 本地编写代码

   • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

2. 调整心态，保持冷静

   • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

3. 输入输出完整性

   • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

4. 快捷键使用

   • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
   • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

5. 浏览器要求

   • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

6. 交卷相关

   • 答题前，务必仔细查看题目示例，避免遗漏要求。
   • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
   • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

7. 时间和分数安排

   • 总时间：150 分钟；总分：400 分。
   • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

8. 考试环境准备

   • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
   • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

9. 技术问题处理

   • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
   • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！