题目描述与示例

一贫如洗的椎夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从 0-N 的子，每个箱子上面有一个数字，箱子排列成一个环，编号最大的箱子的下一个是编号为 0 的箱子。请输出每个箱子贴的数字之后的第一个比它大的数，如果不存在则输出-1。

题目练习网址：https://www.algomooc.com/problem/P2653

输入

输入一个数字字串，数字之间使用逗号分隔，例如: 1,2,3,1；1 ≤ 字串中数字个数 ≤ 10000；-100000≤ 每个数字值 ≤100000

输出

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

示例一

输入

2,5,2

输出

5,-1,5

说明

第一个 2 的下一个更大的数是 5

数字 5 找不到下一个更大的数

第二个 2 的下一个最大的数需要循环搜索，结果也是 5

示例二

输入

3,4,5,6,3

输出

4,5,6,-1,4

解题思路

注意，本题和LC503. 下一个更大元素II完全一致。

寻找下一个更大元素，看到这个字眼应该马上想到单调栈解法。本题的难点在于处理环型数组。

我们仅需在遍历一次数组之后，再次遍历数组，即可以模拟环型数组。因此我们可以用以下代码来遍历数组

# 正序遍历
for i in range(2*n):
    idx = i % n

# 逆序遍历
for i in range(2*n-1, -1, -1):
    idx = i % n

其中n是原数组nums的长度，idx = i % n是元素在原数组nums和答案数组ans中的索引。

除此之外，在更新答案的过程中，还需要再判断ans[idx]是否为-1，如果不是-1，则说明之前已经更新过了，无需重复更新。

剩下部分和常规的单调栈题目没有任何区别。

代码

解法一：正序遍历nums构建单调栈

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 免费获取华为 OD 笔试真题题库和视频

# 输入表示n个操作的数组ops
ops = input().split(" ")

stack = list()      # 初始化一个空栈，在python中可以用list表示栈
isError = False     # 用于标记是否出现异常的标志，初始化为False表示没有异常

for record in ops:  # 遍历整个ops数组
    # 若record为数字，则直接将该数字加入栈中，注意要将str转为int
    if record != 'D' and record != 'C' and record != '+':
        stack.append(int(record))
    # 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
    elif record == 'D' and len(stack) >= 1:
        stack.append(stack[-1] * 2)
    # 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
    elif record == 'C' and len(stack) >= 1:
        stack.pop()
    # 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值
    elif record == '+' and len(stack) >= 2:
        stack.append(stack[-1] + stack[-2])
    # 如果不满足上述的任何条件，说明出现了异常，
    # 将isError修改为True，同时直接退出循环
    else:
        isError = True
        break

# 如果出现异常，输出-1
# 如果没有异常，输出整个栈中数字的总和
print(-1 if isError else sum(stack))


nums = list(map(int, input().split(",")))
n = len(nums)
stack = list()
ans = [-1] * n

for i in range(2*n):
    idx = i % n
    num = nums[idx]
    while(stack and nums[stack[-1]] < num):
        top_idx = stack.pop()
        ans[top_idx] = num
    stack.append(idx)
    
print(",".join(map(str, ans)))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 输入数组并将其分割为整数列表
        String[] input = sc.nextLine().split(",");
        int n = input.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }

        int[] ans = new int[n];       // 初始化答案数组，默认为-1
        Arrays.fill(ans, -1);         

        Stack<Integer> stack = new Stack<>();  // 初始化单调栈

        // 遍历数组两轮，构造单调栈
        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;             // 循环数组索引
            int num = nums[idx];         // 当前数字
            // 栈不为空且栈顶的元素小于当前元素
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                int topIdx = stack.pop(); // 弹出栈顶的索引
                ans[topIdx] = num;        // 更新答案数组
            }
            stack.push(idx);              // 将当前索引加入栈中
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            System.out.print(ans[i]);
            if (i < n - 1) System.out.print(",");
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <sstream>
using namespace std;

int main() {
    string input;
    getline(cin, input);

    // 解析输入字符串为整数数组
    vector<int> nums;
    stringstream ss(input);
    string numStr;
    while (getline(ss, numStr, ',')) {
        nums.push_back(stoi(numStr));
    }

    int n = nums.size();
    vector<int> ans(n, -1);  // 初始化答案数组，默认值为-1
    stack<int> stack;        // 初始化单调栈

    // 遍历数组两轮，构造单调栈
    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n;            // 循环数组索引
        int num = nums[idx];        // 当前数字
        // 栈不为空且栈顶的元素小于当前元素
        while (!stack.empty() && nums[stack.top()] < num) {
            int topIdx = stack.top();
            stack.pop();             // 弹出栈顶的索引
            ans[topIdx] = num;       // 更新答案数组
        }
        stack.push(idx);             // 将当前索引加入栈中
    }

    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << ans[i];
        if (i < n - 1) cout << ",";
    }
    cout << endl;

    return 0;
}

C

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

#define MAX_SIZE 100000  // 假设输入的最大大小

int main() {
    char input[MAX_SIZE];
    fgets(input, sizeof(input), stdin);

    // 解析输入字符串为整数数组
    int nums[MAX_SIZE], ans[MAX_SIZE];
    int stack[MAX_SIZE], top = -1; // 初始化单调栈
    int n = 0;

    // 分割字符串并将每个值转换为整数
    char *token = strtok(input, ",");
    while (token != NULL) {
        nums[n] = atoi(token);
        ans[n] = -1;  // 初始化答案数组为-1
        n++;
        token = strtok(NULL, ",");
    }

    // 遍历数组两轮，构造单调栈
    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n;        // 循环数组索引
        int num = nums[idx];    // 当前数字

        // 栈不为空且栈顶的元素小于当前元素
        while (top >= 0 && nums[stack[top]] < num) {
            int topIdx = stack[top--]; // 弹出栈顶索引
            ans[topIdx] = num;         // 更新答案数组
        }
        stack[++top] = idx;            // 将当前索引压入栈中
    }

    // 输出结果
    for (int i = 0; i < n; i++) {
        printf("%d", ans[i]);
        if (i < n - 1) printf(",");
    }
    printf("\n");

    return 0;
}

Node JavaScript

const readline = require("readline");

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

rl.question('', (input) => {
    // 解析输入字符串为整数数组
    const nums = input.split(',').map(Number);
    const n = nums.length;
    const ans = Array(n).fill(-1); // 初始化答案数组，默认值为-1
    const stack = []; // 初始化单调栈

    // 遍历数组两轮，构造单调栈
    for (let i = 0; i < 2 * n; i++) {
        const idx = i % n;          // 循环数组索引
        const num = nums[idx];      // 当前数字

        // 栈不为空且栈顶的元素小于当前元素
        while (stack.length > 0 && nums[stack[stack.length - 1]] < num) {
            const topIdx = stack.pop();  // 弹出栈顶的索引
            ans[topIdx] = num;           // 更新答案数组
        }
        stack.push(idx);                // 将当前索引加入栈中
    }

    // 输出结果
    console.log(ans.join(","));
    rl.close();
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    // 读取输入
    reader := bufio.NewReader(os.Stdin)
    input, _ := reader.ReadString('\n')
    input = strings.TrimSpace(input)

    // 将输入字符串分割为整数数组
    strNums := strings.Split(input, ",")
    n := len(strNums)
    nums := make([]int, n)
    ans := make([]int, n)

    for i, str := range strNums {
        nums[i], _ = strconv.Atoi(str)
        ans[i] = -1 // 初始化答案数组为-1
    }

    stack := []int{} // 初始化单调栈

    // 遍历数组两轮，构造单调栈
    for i := 0; i < 2*n; i++ {
        idx := i % n       // 循环数组索引
        num := nums[idx]   // 当前数字

        // 栈不为空且栈顶的元素小于当前元素
        for len(stack) > 0 && nums[stack[len(stack)-1]] < num {
            topIdx := stack[len(stack)-1]
            stack = stack[:len(stack)-1] // 弹出栈顶索引
            ans[topIdx] = num            // 更新答案数组
        }
        stack = append(stack, idx) // 将当前索引压入栈中
    }

    // 输出结果
    for i, val := range ans {
        fmt.Print(val)
        if i < n-1 {
            fmt.Print(",")
        }
    }
    fmt.Println()
}

解法二：逆序遍历nums构建单调栈

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 免费获取华为 OD 笔试真题题库和视频

# 输入表示n个操作的数组ops
ops = input().split(" ")

stack = list()      # 初始化一个空栈，在python中可以用list表示栈
isError = False     # 用于标记是否出现异常的标志，初始化为False表示没有异常

for record in ops:  # 遍历整个ops数组
    # 若record为数字，则直接将该数字加入栈中，注意要将str转为int
    if record != 'D' and record != 'C' and record != '+':
        stack.append(int(record))
    # 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
    elif record == 'D' and len(stack) >= 1:
        stack.append(stack[-1] * 2)
    # 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
    elif record == 'C' and len(stack) >= 1:
        stack.pop()
    # 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值
    elif record == '+' and len(stack) >= 2:
        stack.append(stack[-1] + stack[-2])
    # 如果不满足上述的任何条件，说明出现了异常，
    # 将isError修改为True，同时直接退出循环
    else:
        isError = True
        break

# 如果出现异常，输出-1
# 如果没有异常，输出整个栈中数字的总和
print(-1 if isError else sum(stack))


nums = list(map(int, input().split(",")))
n = len(nums)
stack = list()
ans = [-1] * n

for i in range(2*n-1, -1, -1):
    idx = i % n
    num = nums[idx]
    while(stack and nums[stack[-1]] <= num):
        stack.pop()
    if stack:
        ans[idx] = nums[stack[-1]]
    stack.append(idx)
    
print(",".join(map(str, ans)))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入并转换为整数数组
        String[] input = sc.nextLine().split(",");
        int n = input.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }

        int[] ans = new int[n];          // 初始化答案数组，默认值为-1
        Arrays.fill(ans, -1);
        Stack<Integer> stack = new Stack<>();  // 单调栈用于存储索引

        // 逆序遍历数组两轮
        for (int i = 2 * n - 1; i >= 0; i--) {
            int idx = i % n;              // 计算循环数组的索引
            int num = nums[idx];          // 当前数字

            // 将栈中小于等于当前数字的索引弹出
            while (!stack.isEmpty() && nums[stack.peek()] <= num) {
                stack.pop();
            }

            // 如果栈不为空，更新答案数组
            if (!stack.isEmpty()) {
                ans[idx] = nums[stack.peek()];
            }
            // 将当前索引压入栈中
            stack.push(idx);
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            System.out.print(ans[i]);
            if (i < n - 1) System.out.print(",");
        }
        System.out.println();

        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <sstream>
using namespace std;

int main() {
    string input;
    getline(cin, input);

    // 将输入字符串解析为整数数组
    vector<int> nums;
    stringstream ss(input);
    string numStr;
    while (getline(ss, numStr, ',')) {
        nums.push_back(stoi(numStr));
    }

    int n = nums.size();
    vector<int> ans(n, -1);   // 初始化答案数组，默认值为-1
    stack<int> stack;         // 单调栈用于存储索引

    // 逆序遍历数组两轮
    for (int i = 2 * n - 1; i >= 0; i--) {
        int idx = i % n;      // 计算循环数组的索引
        int num = nums[idx];  // 当前数字

        // 将栈中小于等于当前数字的索引弹出
        while (!stack.empty() && nums[stack.top()] <= num) {
            stack.pop();
        }

        // 如果栈不为空，更新答案数组
        if (!stack.empty()) {
            ans[idx] = nums[stack.top()];
        }
        // 将当前索引压入栈中
        stack.push(idx);
    }

    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << ans[i];
        if (i < n - 1) cout << ",";
    }
    cout << endl;

    return 0;
}

C

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

#define MAX_SIZE 100000  // 假设输入的最大大小

int main() {
    char input[MAX_SIZE];
    fgets(input, MAX_SIZE, stdin);

    // 将输入字符串解析为整数数组
    int nums[MAX_SIZE];
    int n = 0;
    char *token = strtok(input, ",");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",");
    }

    int ans[MAX_SIZE];
    int stack[MAX_SIZE];
    int top = -1;

    // 初始化答案数组，默认值为-1
    for (int i = 0; i < n; i++) {
        ans[i] = -1;
    }

    // 逆序遍历数组两轮
    for (int i = 2 * n - 1; i >= 0; i--) {
        int idx = i % n;  // 计算循环数组的索引
        int num = nums[idx];

        // 将栈中小于等于当前数字的索引弹出
        while (top >= 0 && nums[stack[top]] <= num) {
            top--;
        }

        // 如果栈不为空，更新答案数组
        if (top >= 0) {
            ans[idx] = nums[stack[top]];
        }
        // 将当前索引压入栈中
        stack[++top] = idx;
    }

    // 输出结果
    for (int i = 0; i < n; i++) {
        printf("%d", ans[i]);
        if (i < n - 1) printf(",");
    }
    printf("\n");

    return 0;
}

Node JavaScript

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

rl.question("", (input) => {
    // 将输入字符串解析为整数数组
    const nums = input.trim().split(",").map(Number);
    const n = nums.length;
    const ans = Array(n).fill(-1);  // 初始化答案数组
    const stack = [];  // 用于存储索引的单调栈

    // 逆序遍历数组两轮
    for (let i = 2 * n - 1; i >= 0; i--) {
        const idx = i % n;  // 计算循环数组的索引
        const num = nums[idx];

        // 将栈中小于等于当前数字的索引弹出
        while (stack.length > 0 && nums[stack[stack.length - 1]] <= num) {
            stack.pop();
        }

        // 如果栈不为空，更新答案数组
        if (stack.length > 0) {
            ans[idx] = nums[stack[stack.length - 1]];
        }
        // 将当前索引加入栈中
        stack.push(idx);
    }

    // 输出结果
    console.log(ans.join(","));
    rl.close();
});

时空复杂度

时间复杂度：O(N)。仅需两次遍历数组nums，O(2N) = O(N)。

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

N为原数组nums的长度。