You are given a sequence of n integers a₁ … aₙ. For each position i, find the nearest aⱼ to the right of i (j > i) that is greater than aᵢ (equal does not count). If there is none, the answer is -1. Print the n answers in position order on one line, separated by spaces.
The first line gives n, and the second line gives a₁ … aₙ separated by spaces.
Input
1 ≤ n ≤ 10,000, 1 ≤ aᵢ ≤ 10⁹
Output
n answers (one line, separated by spaces)
Example 1 · stdin
7
2 7 3 5 4 6 8
stdout
7 8 5 6 6 8 -1
Example 2 · stdin
5
4 4 1 4 9
stdout
9 9 4 9 -1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Scanning to the right from every position makes n²/2 = 50 million comparisons on a decreasing sequence. C and C++ survive, but Craykon passes its execution-step limit (about 50 million) and stops, and Python takes seconds. Keep a stack of 'positions that have not met a greater number yet': when a new number x comes, pop while the top's value is less than x, writing x as their answer, then push x's position. Each position is pushed once and popped once, 2n operations in all. Three traps: popping with <= treats an equal number as 'greater' (the problem wants <). The 'first greater' is not 'the largest to the right' (in 1 5 3 4 the answer for 3 is 4, not 5). And push positions, not values, so you can write each answer in its place. Using a stack: Python list append()/pop()/stack[-1], JavaScript/TypeScript array push()/pop()/stack[stack.length - 1] (in TS pop() is number | undefined, hence the !), Java ArrayDeque with push()/pop()/peek() (preferred over the old Stack class), C# Stack<int> with Push()/Pop()/Peek(), C++ std::stack with top()/pop() (pop() returns nothing, so read top() first), C an array plus a top variable. Craykon uses the end of a list as the top: look with stack[stack.Count - 1] and pop with stack.RemoveAt(stack.Count - 1).
Pythonmain.py · 10 lines
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)))
JavaScriptmain.js · 11 lines
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(" "));
TypeScriptmain.ts · 12 lines
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(" "));
JavaMain.java · 30 lines
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); }}
C#Main.cs · 24 lines
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)); }}
C++main.cpp · 24 lines
#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';}
Cmain.c · 21 lines
#include <stdio.h>#define MAXN 10000int 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;}
Craykonmain.cray · 15 lines
n = Console.ReadLine().ToNumber();a = Console.ReadNumbers();answer = NewList(n, -1);stack = []; // 아직 더 큰 수를 못 만난 자리들. 맨 위는 stack[stack.개수 - 1]for (i = 0; i < n; i++){ while (stack.Count > 0 && a[stack[stack.Count - 1]] < a[i]) { answer[stack[stack.Count - 1]] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' stack.RemoveAt(stack.Count - 1); } stack.Add(i);}Console.WriteLine(answer);