返回目录

题目描述

在学校中，N个小朋友站成一队， 第i个小朋友的身高为height[i]，

第i个小朋友可以看到的第一个比自己身高更高的小朋友j，那么j是i的好朋友(要求j > i)。

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

小朋友人数范围是 [0, 40000]。

输入描述

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

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

输出描述

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

Python算法源码

def get_higher_index(arr):
    stack = []  # 初始化一个栈，用于存储待比较的元素及其索引
    res = [0] * len(arr)  # 初始化一个结果列表，用于存储每个元素第一次遇到比它高的人的索引

    for i, ele in enumerate(arr):  # 遍历输入的数组
        index = i  # 当前元素的索引

        while True:
            if not stack:  # 如果栈为空，直接将当前元素入栈
                stack.append((ele, index))
                break

            peek_ele, peek_index = stack[-1]  # 获取栈顶元素

            if ele > peek_ele:  # 如果当前元素比栈顶元素高
                res[peek_index] = index  # 更新栈顶元素对应的结果为当前元素的索引
                stack.pop()  # 弹出栈顶元素
            else:
                stack.append((ele, index))  # 否则，将当前元素入栈
                break

    return res  # 返回结果列表

if __name__ == "__main__":
    n = int(input())  # 输入数组的长度
    arr = list(map(int, input().split()[:n]))  # 输入数组

    result = get_higher_index(arr)  # 调用函数获取结果
    print(" ".join(map(str, result)))  # 将结果列表转换为字符串并输出

C算法源码

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    scanf("%d", &n);
  
    // 输入小朋友的身高
    int heights[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &heights[i]);
    }
  
    // 用于存储每个小朋友的好朋友位置
    int friendIndexes[n];
  
    // 使用栈来记录每个小朋友的位置
    int stack[n];
    int top = -1;
    stack[++top] = 0;
    for (int i = 1; i < n; i++) {
        while (top != -1 && heights[i] > heights[stack[top]]) {
            // 如果当前小朋友的身高大于栈顶小朋友的身高，则栈顶小朋友的好朋友位置为当前小朋友的位置
            friendIndexes[stack[top--]] = i;
        }
        stack[++top] = i;
    }
  
    // 输出每个小朋友的好朋友位置
    for (int i = 0; i < n; i++) {
        printf("%d ", friendIndexes[i]);
    }
  
    return 0;
}

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[] arr = new int[n]; // 存储小朋友的身高
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt(); // 输入小朋友的身高
        }
    
        // 调用getResult方法获取结果并输出
        System.out.println(getResult(arr));
    }
  
    // 获取结果的方法
    public static String getResult(int[] arr) {
        Stack<int[]> stack = new Stack<>(); // 使用栈来记录每个小朋友的位置
        int[] res = new int[arr.length]; // 存储每个小朋友的好朋友位置

        for (int i = 0; i < arr.length; i++) {
            int ele = arr[i]; // 获取当前小朋友的身高

            // 循环处理当前小朋友
            while (true) {
                if (stack.isEmpty()) {
                    stack.push(new int[]{ele, i}); // 如果栈为空，直接将当前小朋友入栈
                    break;
                }

                int[] peek = stack.peek(); // 获取栈顶元素
                int peekEle = peek[0]; // 栈顶小朋友的身高
                int peekIndex = peek[1]; // 栈顶小朋友的位置

                if (ele > peekEle) { // 如果当前小朋友的身高大于栈顶小朋友的身高
                    res[peekIndex] = i; // 栈顶小朋友的好朋友位置为当前小朋友的位置
                    stack.pop(); // 弹出栈顶小朋友
                } else {
                    stack.push(new int[]{ele, i}); // 否则将当前小朋友入栈
                    break;
                }
            }
        }

        // 构造结果字符串
        StringBuilder sb = new StringBuilder();
        for (int num : res) {
            sb.append(num).append(" ");
        }
        return sb.toString().trim(); // 返回结果字符串
    }
}