右边第一个更大的数
给出由 n 个整数组成的数列 a₁ … aₙ。
对每个位置 i，求在 i 右边（j > i）且大于 aᵢ（相等不算）的数中最近的那个 aⱼ。
如果没有，答案为 -1。
按位置顺序把 n 个答案用空格隔开输出在一行。
第一行给出 n，第二行给出用空格隔开的 a₁ … aₙ。
- 输入
- 1 ≤ n ≤ 10,000，1 ≤ aᵢ ≤ 10⁹
- 输出
- n 个答案（一行，空格隔开）
7 2 7 3 5 4 6 8
7 8 5 6 6 8 -1
5 4 4 1 4 9
9 9 4 9 -1
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
对每个位置都向右扫描，在递减数列上要比较 n²/2 = 五千万次。
C、C++ 撑得住，但 Craykon 会超过执行步数上限（约五千万）而停止，Python 也要好几秒。
用栈存放「还没遇到更大数的位置」：来了新数 x 时，只要栈顶的值小于 x 就弹出并把答案写成 x，最后把 x 的位置压入。
每个位置压入一次、弹出一次，总共 2n 次。
三个陷阱：弹出条件写成 <= 会把相等的数当成「更大」（题目要 <）。
「第一个更大的数」不是「右边最大的数」（1 5 3 4 中 3 的答案是 4 而不是 5）。
另外栈里要放位置而不是值，才能把答案写回原处。
栈的用法：Python 列表 append()/pop()/stack[-1]，JavaScript/TypeScript 数组 push()/pop()/stack[stack.length - 1]（TS 中 pop() 的类型是 number | undefined，所以加 !），Java ArrayDeque 的 push()/pop()/peek()（比老的 Stack 类更推荐），C# Stack<int> 的 Push()/Pop()/Peek()，C++ std::stack 的 top()/pop()（pop() 不返回值，所以先读 top()），C 用数组加 top 变量。
Craykon 把列表末尾当作栈顶，用 stack[stack.数量 - 1] 查看，用 stack.按位置移除(stack.数量 - 1) 弹出。
n = int(input())a = list(map(int, input().split())) answer = [-1] * nstack = [] # 아직 더 큰 수를 못 만난 자리들. 값은 아래에서 위로 줄어든다(같을 수는 있다)for i, x in enumerate(a): while stack and a[stack[-1]] < x: # x가 그 자리들의 '오른쪽 첫 큰 수' answer[stack.pop()] = x stack.append(i)print(" ".join(map(str, answer)))const [n, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); const answer = new Array(n).fill(-1);const stack = []; // 아직 더 큰 수를 못 만난 자리들. 값은 아래에서 위로 줄어든다(같을 수는 있다)for (let i = 0; i < n; i++) { while (stack.length > 0 && a[stack[stack.length - 1]] < a[i]) { answer[stack.pop()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.push(i);}console.log(answer.join(" "));import { readFileSync } from "node:fs";const [n, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); const answer: number[] = new Array(n).fill(-1);const stack: number[] = []; // 아직 더 큰 수를 못 만난 자리들. 값은 아래에서 위로 줄어든다(같을 수는 있다)for (let i = 0; i < n; i++) { while (stack.length > 0 && a[stack[stack.length - 1]] < a[i]) { answer[stack.pop()!] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.push(i);}console.log(answer.join(" "));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringTokenizer st = new StringTokenizer(br.readLine()); int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); int[] answer = new int[n]; Arrays.fill(answer, -1); Deque<Integer> stack = new ArrayDeque<>(); // 아직 더 큰 수를 못 만난 자리들 for (int i = 0; i < n; i++) { while (!stack.isEmpty() && a[stack.peek()] < a[i]) { answer[stack.pop()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.push(i); } StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) out.append(i > 0 ? " " : "").append(answer[i]); System.out.println(out); }}using System;using System.Collections.Generic;using System.Linq; class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int[] answer = Enumerable.Repeat(-1, n).ToArray(); var stack = new Stack<int>(); // 아직 더 큰 수를 못 만난 자리들 for (int i = 0; i < n; i++) { while (stack.Count > 0 && a[stack.Peek()] < a[i]) { answer[stack.Pop()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.Push(i); } Console.WriteLine(string.Join(" ", answer)); }}#include <iostream>#include <stack>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<int> a(n); for (int& x : a) std::cin >> x; std::vector<int> answer(n, -1); std::stack<int> st; // 아직 더 큰 수를 못 만난 자리들 for (int i = 0; i < n; i++) { while (!st.empty() && a[st.top()] < a[i]) { answer[st.top()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' st.pop(); } st.push(i); } for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << answer[i]; std::cout << '\n';}#include <stdio.h> #define MAXN 10000 int main(void) { static int a[MAXN], answer[MAXN], stack[MAXN]; int n, top = 0; /* stack[0..top-1]: 아직 더 큰 수를 못 만난 자리들 */ scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) { answer[i] = -1; while (top > 0 && a[stack[top - 1]] < a[i]) { answer[stack[--top]] = a[i]; /* a[i]가 그 자리의 '오른쪽 첫 큰 수' */ } stack[top++] = i; } for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", answer[i]); putchar('\n'); return 0;}n = 控制台.读行().转数字();a = 控制台.读数字(); answer = 新列表(n, -1);stack = []; // 아직 더 큰 수를 못 만난 자리들. 맨 위는 stack[stack.개수 - 1]循环 (i = 0; i < n; i++){ 当 (stack.数量 > 0 && a[stack[stack.数量 - 1]] < a[i]) { answer[stack[stack.数量 - 1]] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' stack.按位置移除(stack.数量 - 1); } stack.添加(i);}控制台.输出(answer);