"""
p51 — Daily Temperatures (LeetCode 739, MEDIUM).

For each index i, answer[i] = number of days until a STRICTLY warmer temperature,
or 0 if none exists.

Three implementations:
    daily_temperatures_stack   — forward monotonic decreasing stack. O(n).
    daily_temperatures_reverse — reverse iteration variant. O(n).
    daily_temperatures_brute   — nested loop O(n^2) oracle.
"""
from __future__ import annotations
import random
from typing import List


def daily_temperatures_stack(T: List[int]) -> List[int]:
    n = len(T)
    ans = [0] * n
    # INVARIANT: T-values at stack indices are STRICTLY DECREASING from bottom to top.
    stack: List[int] = []
    for i, t in enumerate(T):
        # Resolve every index whose temperature is broken by t (i.e., t > T[stack[-1]]).
        while stack and T[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    # Anything left in stack has no warmer future day; ans[j] = 0 already.
    return ans


def daily_temperatures_reverse(T: List[int]) -> List[int]:
    n = len(T)
    ans = [0] * n
    # INVARIANT: T-values at stack indices are STRICTLY DECREASING (right-to-left fill).
    # Top of stack = nearest greater-or-equal candidate to the right of current i.
    stack: List[int] = []
    for i in range(n - 1, -1, -1):
        # Discard candidates that aren't STRICTLY greater than T[i].
        while stack and T[stack[-1]] <= T[i]:
            stack.pop()
        ans[i] = stack[-1] - i if stack else 0
        stack.append(i)
    return ans


def daily_temperatures_brute(T: List[int]) -> List[int]:
    n = len(T)
    ans = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if T[j] > T[i]:
                ans[i] = j - i
                break
    return ans


def edge_cases() -> None:
    # LC canonical
    assert daily_temperatures_stack([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
    assert daily_temperatures_reverse([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]

    # Strictly increasing
    assert daily_temperatures_stack([30, 40, 50, 60]) == [1, 1, 1, 0]
    # Strictly decreasing
    assert daily_temperatures_stack([90, 80, 70, 60]) == [0, 0, 0, 0]
    # All equal — STRICT means no answer
    assert daily_temperatures_stack([50, 50, 50, 50]) == [0, 0, 0, 0]
    # Single
    assert daily_temperatures_stack([42]) == [0]
    # Empty (defensive)
    assert daily_temperatures_stack([]) == []
    # Ties broken by next strict
    assert daily_temperatures_stack([50, 50, 51]) == [2, 1, 0]

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(1000):
        n = rng.randint(0, 50)
        T = [rng.randint(30, 100) for _ in range(n)]
        a = daily_temperatures_stack(T)
        b = daily_temperatures_reverse(T)
        c = daily_temperatures_brute(T)
        assert a == b == c, f"trial {trial}: T={T} a={a} b={b} c={c}"
    print("stress_test: 1000 random trials — stack, reverse, brute all agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")