İçeriğe geç

Sonraki büyük değer araması

Kolay#monotonic-stack#hash-map~15 dk

Görev tanımı

Problem

Sana birbirinden farklı tam sayılardan oluşan bir nums listesi ve değerlerinin hepsi nums'ta bir yerde görünen bir queries listesi veriliyor. Her sorgu değeri için nums'ta onun sağındaki, ondan büyük ilk değeri bul; arkasından büyük bir değer gelmiyorsa -1. Cevapları sorgu sırasıyla döndür.

Örnekler

Input:  nums = [4, 1, 3, 6, 2, 5], queries = [1, 3, 2, 6]
Output: [3, 6, 5, -1]
Neden: 1'i 3, 3'ü 6, 2'yi 5 izliyor; 6'dan sonraki hiçbir şey daha büyük değil
Input:  nums = [5, 4, 3, 2, 1], queries = [4, 1]
Output: [-1, -1]
Neden: liste yalnız düşüyor, yani hiçbir değerin ardından büyüğü gelmiyor
Input:  nums = [7], queries = [7]
Output: [-1]
Neden: edge case: tek bir değerin sağında hiçbir şey yok

İpuçları

0 / 3

Hedef zaman
O(n + q)
Hedef alan
O(n + q)

Kısıtlar

  • nums holds distinct integers
  • every query value appears in nums

Kodda değil de fikirde mi takıldın? Monoton stack bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case