(B卷,200分)- 阿里巴巴找黄金宝箱(IV)（Java & JS & Python & C）

题目描述

一贫如洗的樵夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从0-N的箱子，每个箱子上面有一个数字，箱子排列成一个环，编号最大的箱子的下一个是编号为0的箱子。

请输出每个箱了贴的数字之后的第一个比它大的数，如果不存在则输出-1。

输入描述

输入一个数字字串，数字之间使用逗号分隔，例如: 1,2,3,1

• 1 ≤ 字串中数字个数 ≤ 10000:
• -100000 ≤ 每个数字值 ≤ 100000

输出描述

下一个大的数列表，以逗号分隔，例如: 2,3,6,-1,6

用例

题目解析

本题就是

的换皮题，解析可以参考链接博客。

Java算法源码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] arr = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    System.out.println(getResult(arr));
  }

  public static String getResult(int[] arr) {
    LinkedList<int[]> stack = new LinkedList<>();

    int[] res = new int[arr.length];
    Arrays.fill(res, -1);

    findNextBig(arr, stack, res);

    if (stack.size() != 1) findNextBig(arr, stack, res);

    StringJoiner sj = new StringJoiner(",");
    for (int v : res) {
      sj.add(v + "");
    }
    return sj.toString();
  }

  public static void findNextBig(int[] arr, LinkedList<int[]> stack, int[] res) {
    for (int i = 0; i < arr.length; i++) {
      int ele = arr[i];
      while (true) {
        if (stack.size() == 0) {
          stack.add(new int[] {ele, i});
          break;
        } else {
          int[] peek = stack.get(stack.size() - 1);
          int peekEle = peek[0];
          int peekIdx = peek[1];

          if (ele > peekEle) {
            res[peekIdx] = ele;
            stack.removeLast();
          } else {
            stack.add(new int[] {ele, i});
            break;
          }
        }
      }
    }
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const arr = line.split(",").map(Number);
  console.log(getResult(arr));
});

function getResult(arr) {
  const stack = [];
  const res = new Array(arr.length).fill(-1);

  findNextBig(arr, stack, res);

  if (stack.length != 1) findNextBig(arr, stack, res);

  return res.join(",");
}

function findNextBig(arr, stack, res) {
  for (let i = 0; i < arr.length; i++) {
    const ele = arr[i];

    while (true) {
      if (stack.length == 0) {
        stack.push([ele, i]);
        break;
      } else {
        const [peekEle, peekIdx] = stack.at(-1);

        if (ele > peekEle) {
          res[peekIdx] = ele;
          stack.pop();
        } else {
          stack.push([ele, i]);
          break;
        }
      }
    }
  }
}

Python算法源码

# 输入获取
arr = list(map(int, input().split(",")))


def findNextBig(arr, stack, res):
    for i in range(len(arr)):
        ele = arr[i]

        while True:
            if len(stack) == 0:
                stack.append([ele, i])
                break
            else:
                peekEle, peekIdx = stack[-1]

                if ele > peekEle:
                    res[peekIdx] = ele
                    stack.pop()
                else:
                    stack.append([ele, i])
                    break


# 算法入口
def getResult():
    stack = []
    res = [-1] * len(arr)

    findNextBig(arr, stack, res)

    if len(stack) != 1:
        findNextBig(arr, stack, res)

    return ",".join(map(str, res))


# 算法调用
print(getResult())

C算法源码

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

#define MAX_SIZE 10000

/**
 * 栈结构定义
 * 容器 stack 数组，容量上限MAX_SIZE
 * 栈中元素个数 stack_size
 * 压栈操作 stack_push
 * 弹栈操作 stack_pop
 */
int *stack[MAX_SIZE];
int stack_size = 0;

void stack_push(int *ele) {
    if (stack_size < MAX_SIZE) {
        stack[stack_size++] = ele;
    }
}

int *stack_pop() {
    if (stack_size > 0) {
        return stack[--stack_size];
    }
    return NULL;
}


/**
 * 算法逻辑
 */
int nums[MAX_SIZE];
int nums_size = 0;

char *getResult();

void findNextBig(int *res);

int main() {
    // 输入获取
    while (scanf("%d", &nums[nums_size++])) {
        if (getchar() != ',') break;
    }

    // res[i]记录的是比nums[i]大的下一个值
    int res[MAX_SIZE];
    for (int i = 0; i < nums_size; i++) {
        res[i] = -1;
    }

    findNextBig(res);
    if (stack_size != 1) findNextBig(res);

    // 输出打印
    for (int i = 0; i < nums_size - 1; i++) {
        printf("%d,", res[i]);
    }
    printf("%dn", res[nums_size - 1]);

    return 0;
}

void findNextBig(int *res) {
    for (int i = 0; i < nums_size; i++) {
        int num = nums[i];

        int *p = (int *) malloc(sizeof(int) * 2);
        p[0] = num;
        p[1] = i;

        while (1) {
            if (stack_size == 0) {
                stack_push(p);
                break;
            }

            int *peek = stack[stack_size - 1];
            int peekNum = peek[0];
            int peekIdx = peek[1];

            if (num > peekNum) {
                res[peekIdx] = num;
                // stack_pop出来的就是前面动态申请的p指针指向的内存，此时pop出来后，需要注意释放p指针指向的内存
                free(stack_pop());
            } else {
                stack_push(p);
                break;
            }
        }
    }
}