【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【单调栈】2023C-找朋友【欧弟算法】全网注释最详细分类最全的华为OD真题题解

本文主要是介绍【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【单调栈】2023C-找朋友【欧弟算法】全网注释最详细分类最全的华为OD真题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有华为OD考试扣扣交流群可加：948025485
可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1336了解算法冲刺训练

题目描述与示例

题目描述

在学校中，N个小朋友站成一队， 第i个小朋友的身高为height[i]，第i个小朋友可以看到的右边的第一个比自己身高更高的小朋友j，那么j是i的好朋友（j > i）。请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用0代替。小朋友人数范围是 [0, 40000]。

输入描述

第一行输入N，表示有N个小朋友

第二行输入N个小朋友的身高height[i]，都是整数

输出描述

输出N个小朋友的好朋友的位置

示例一

输入

2
100 95

输出

0 0

示例二

输入

8
123 124 125 121 119 122 126 123

输出

1 2 6 5 5 6 0 0

解题思路

注意，本题和LC739. 每日温度非常类似。区别在于，本题需要找到的是右边下一个更大元素的索引，而非与当前元素的间隔，显然变得更加简单了。

我们讲过，类似这种要求寻找左边/右边最近的更大/更小元素的题目，均可以使用单调栈来完成。

对于单调栈的题目，既可以正序遍历也可以逆序遍历数组来完成，重点在于理解单调栈的原理，同学们只需要选择适合自己理解的方法来完成即可。以下表格总结了两种不同遍历顺序的异同点。

	正序遍历	逆序遍历
单调栈顺序	栈中储存的索引所对应在原数组中的元素大小，从栈底至栈顶单调递减，即更大的数（的下标）位于栈底
入栈时机	栈顶元素反复出栈并修改ans之后，进行入栈。且入栈元素为当前下标i，而非身高h
修改ans时机	i为preIndex的下一个更大元素的下标，在出栈过程中，即在while内修改ans[preIndex]	stack[-1]为i的下一个更大元素的下标，在出栈结束后，即在while外修改ans[i]
出栈条件	h > height[stack[-1]]	h >= height[stack[-1]]

代码

解法一

Python

正序遍历height构建单调栈。

# 题目：2023Q1A-找朋友
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：单调栈-正序遍历原数组
# 代码看不懂的地方，请直接在群上提问# 输入小朋友个数n
n = int(input())
# 输入N个小朋友的高度数组
height = list(map(int, input().split()))# 构建一个单调栈，用来存放不同小朋友的身高的索引
# 栈中储存的索引所对应在height中的元素大小，从栈底至栈顶单调递减
# 即更大的数（的下标）位于栈底
stack = list()# 构建列表ans，用来保存输出结果
# 初始化其中所有的元素均为0
ans = [0] * n# 从头开始遍历每一个小朋友的身高
for i, h in enumerate(height):# 第i个小朋友的身高h，需要不断地与栈顶元素比较# 如果栈顶元素存在并且h【大于】栈顶元素stack[-1]# 意味着栈顶元素找到了右边最近的比他更高的身高hwhile len(stack) > 0 and h > height[stack[-1]]:# 首先获取栈顶元素的值，也就是上一个比h小的身高的索引值preIndex = stack.pop()# i即为preIndex这个索引所对应的，下一个最近身高ans[preIndex] = i# 再把当前小朋友身高的下标i存放到栈中# 注意：所储存的是下标i，而不是身高hstack.append(i)# ans中的int元素转成str后才能合并成字符串
print(" ".join(map(str, ans)))

Java

import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] height = new int[n];for (int i = 0; i < n; i++) {height[i] = scanner.nextInt();}Stack<Integer> stack = new Stack<>();int[] ans = new int[n];// 从头开始遍历每一个小朋友的身高for (int i = 0; i < n; i++) {int h = height[i];// 第i个小朋友的身高h，需要不断地与栈顶元素比较// 如果栈顶元素存在并且h > 栈顶元素 stack.peek()// 意味着栈顶元素找到了右边最近的比他更高的身高hwhile (!stack.isEmpty() && h > height[stack.peek()]) {// 首先获取栈顶元素的值，也就是上一个比h小的身高的索引值int preIndex = stack.pop();// i即为preIndex这个索引所对应的，下一个最近身高ans[preIndex] = i;}// 再把当前小朋友身高的下标i存放到栈中stack.push(i);}// ans中的int元素转成str后才能合并成字符串for (int i = 0; i < n; i++) {System.out.print(ans[i] + " ");}System.out.println();}
}

C++

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
using namespace std;int main() {int n;cin >> n;cin.ignore();vector<int> height(n);for (int i = 0; i < n; i++) {cin >> height[i];}stack<int> stk;vector<int> ans(n, 0);for (int i = 0; i < n; i++) {int h = height[i];while (!stk.empty() && h > height[stk.top()]) {int preIndex = stk.top();stk.pop();ans[preIndex] = i;}stk.push(i);}for (int i = 0; i < n; i++) {cout << ans[i] << " ";}cout << endl;return 0;
}

解法二

逆序遍历height构建单调栈。

Python

# 题目：2023Q1A-找朋友
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：单调栈-逆序遍历原数组
# 代码看不懂的地方，请直接在群上提问# 输入小朋友个数n
n = int(input())
# 输入N个小朋友的高度数组
height = list(map(int, input().split()))# 构建一个单调栈，用来存放不同小朋友的身高的索引
# 栈中储存的索引所对应在height中的元素大小，从栈底至栈顶单调递增
# 即更大的数（的下标）位于栈底
stack = list()# 构建列表ans，用来保存输出结果
# 初始化其中所有的元素均为0
ans = [0] * n# 逆序遍历每一个小朋友的身高
for i in range(n-1, -1, -1):h = height[i]# 第i个小朋友的身高h，需要不断地与栈顶元素比较# 如果栈顶元素存在并且h【大于等于】栈顶元素stack[-1]# 说明栈顶元素stack[-1]并不是身高h右边最近的比h更大的元素# 需要将栈顶元素弹出，继续寻找比h大的栈顶元素while len(stack) > 0 and h >= height[stack[-1]]:# 栈顶元素下标对应的身高不大于当前身高h，不是符合要求的更大身高，弹出stack.pop()# 完成弹出后，如果栈顶仍存在元素，说明stack[-1]所对应的身高，是严格比h大的下一个身高if len(stack) > 0:# ans[i]修改为stack[-1]ans[i] = stack[-1]# 再把当前小朋友身高的下标i存放到栈中# 注意：所储存的是下标i，而不是身高hstack.append(i)# ans中的int元素转成str后才能合并成字符串
print(" ".join(map(str, ans)))

Java

import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] height = new int[n];for (int i = 0; i < n; i++) {height[i] = scanner.nextInt();}Stack<Integer> stack = new Stack<>();int[] ans = new int[n];// 逆序遍历每一个小朋友的身高for (int i = n - 1; i >= 0; i--) {int h = height[i];// 第i个小朋友的身高h，需要不断地与栈顶元素比较// 如果栈顶元素存在并且h >= 栈顶元素 stack.peek()// 说明栈顶元素 stack.peek() 并不是身高h右边最近的比h更大的元素// 需要将栈顶元素弹出，继续寻找比h大的栈顶元素while (!stack.isEmpty() && h >= height[stack.peek()]) {// 栈顶元素下标对应的身高不大于当前身高h，不是符合要求的更大身高，弹出stack.pop();}// 完成弹出后，如果栈顶仍存在元素，说明 stack.peek() 所对应的身高，是严格比h大的下一个身高if (!stack.isEmpty()) {// ans[i] 修改为 stack.peek()ans[i] = stack.peek();}// 再把当前小朋友身高的下标i存放到栈中stack.push(i);}// ans中的int元素转成str后才能合并成字符串for (int i = 0; i < n; i++) {System.out.print(ans[i] + " ");}System.out.println();}
}

C++

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
using namespace std;int main() {int n;cin >> n;cin.ignore();vector<int> height(n);for (int i = 0; i < n; i++) {cin >> height[i];}stack<int> stk;vector<int> ans(n, 0);for (int i = n - 1; i >= 0; i--) {int h = height[i];while (!stk.empty() && h >= height[stk.top()]) {stk.pop();}if (!stk.empty()) {ans[i] = stk.top();}stk.push(i);}for (int i = 0; i < n; i++) {cout << ans[i] << " ";}cout << endl;return 0;
}

时空复杂度

时间复杂度：O(N)。不管是正序还是逆序遍历，均仅需一次遍历height数组。

空间复杂度：O(N)。单调栈所占用的额外空间。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多

这篇关于【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【单调栈】2023C-找朋友【欧弟算法】全网注释最详细分类最全的华为OD真题题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---