华为od（D卷）找朋友

题目描述

在学校中，N 个小朋友站成一队， 第 i 个小朋友的身高为 height[i]，第 i 个小朋友可以看到的右边的第一个比自己身高更高的小朋友 j，那么 j 是 i 的好朋友（j > i）。

请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用 0 代替。小朋友人数范围是 [0, 40000]。

输入描述

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

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

输出描述

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

示例1

输入
2
100 95

输出
0 0

示例2

输入：
8
123 124 125 121 119 122 126 123

输出：
1 2 6 5 5 6 0 0

思路

1. “下一个” “相邻”: 利用栈
2. 求下一个比自己小的，单调递减栈，栈顶最大。
   求下一个比自己大的，单调递增栈，栈顶最小。
3. 栈内存放的内容是索引的值。
4. 注意示例2的数据：好朋友可以相同。

代码

public class Demo03 {public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNextInt()){int count = in.nextInt();int[] height = new int[count];for (int i = 0; i < count; i++) {height[i] = in.nextInt();}int[]friend = new int[count];// 单调递增栈Stack<Integer> index = new Stack<>();for (int i = 0; i < count; i++) {int h = height[i];// 好朋友可以相同,连续获取while (!index.empty() && h > height[index.peek()] ) {// 栈里的人匹配到好朋友了。friend[index.pop()] = i;}index.push(i);//好朋友只有一个，
//                if (!index.empty() && h > height[index.peek()] ) {
//                    // 栈里的人匹配到好朋友了。
//                    friend[index.pop()] = i;
//                } else {
//                    index.push(i);
//
//                }}System.out.println(Arrays.stream(friend).mapToObj(String::valueOf).collect(Collectors.joining(",")));}}}