Show problems as
Classic problem #739MediumArrayStackMonotonic Stack

Daily Temperatures

Real-world version: Nights Until a Fuller House
Tracked in this browser only
Read Daily Temperatures on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMonotonic Stack · Stacks & Queues, animated step by step

A repertory theatre keeps a run log: occupancy[i] is the percentage of seats sold on the i-th night of the run, in performance order.

The manager wants to know, for every night, how soon the house got fuller than it was that night. Build an array waits of the same length where waits[i] counts the nights between night i and the earliest night after it whose percentage is strictly above occupancy[i]. Nights that tie do not count as fuller. Put 0 in waits[i] when no later night in the run beats night i.

Examples

Example 1

Input
occupancy = [64, 71, 68, 68, 95, 84, 100]
Output
[1, 3, 2, 1, 2, 1, 0]

Night 1 already beats night 0, so the first entry is 1. Night 2 and night 3 both sold the same 68 percent, so night 2 has to skip past night 3 and wait for the 95 percent night.

Example 2

Input
occupancy = [88, 76, 55]
Output
[0, 0, 0]

The run only thins out, so no night is ever followed by a fuller one.

Example 3

Input
occupancy = [45, 45, 45]
Output
[0, 0, 0]

Every night sells the same share of the house, and an equal night is not a fuller night.

Constraints

  • 1 <= occupancy.length <= 10^5
  • 30 <= occupancy[i] <= 100

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def nights_until_fuller(occupancy: list[int]) -> list[int]:
Java
public int[] nightsUntilFuller(int[] occupancy)

More on the same topics