A cold-storage facility records one integer temperature reading at a time.

Design a monitor that can quickly report the highest temperature among a fixed number of the most recently recorded readings.

Class

ColdStorageMonitor

Constructor

ColdStorageMonitor

ColdStorageMonitor(int recentReadingLimit)

• Creates an empty temperature monitor.
• recentReadingLimit is the maximum number of recent readings considered when finding the highest temperature.

Methods

recordTemperature

void recordTemperature(int temperature)

Records a new temperature reading.

getHighestRecentTemperature

int getHighestRecentTemperature()

Returns the highest temperature among the most recent readings.

Rules

• Readings are considered in the order in which they are recorded.
• Only the latest recentReadingLimit readings are considered.
• If fewer readings have been recorded, all available readings are considered.
• Older readings stop affecting the result when they leave the recent group.
• Calling getHighestRecentTemperature does not change the recorded readings.

Constraints

• 1 ≤ recentReadingLimit ≤ 100,000
• -1,000,000,000 ≤ temperature ≤ 1,000,000,000
• At most 100,000 method calls will be made.
• getHighestRecentTemperature will be called only after at least one temperature has been recorded.

Expected Efficiency

• recordTemperature should run in O(1) amortized time.
• getHighestRecentTemperature should run in O(1) time.
• The monitor should use O(recentReadingLimit) space.

Example 1

ColdStorageMonitor(recentReadingLimit = 3)

recordTemperature(temperature = 18)

recordTemperature(temperature = 24)

recordTemperature(temperature = 21)

getHighestRecentTemperature() returns 24.

recordTemperature(temperature = 16)

getHighestRecentTemperature() returns 24 because the three most recent readings are 24, 21, and 16.

recordTemperature(temperature = 29)

getHighestRecentTemperature() returns 29 because the three most recent readings are 21, 16, and 29.

Example 2

ColdStorageMonitor(recentReadingLimit = 2)

recordTemperature(temperature = -8)

recordTemperature(temperature = -3)

getHighestRecentTemperature() returns -3.

recordTemperature(temperature = -10)

getHighestRecentTemperature() returns -3 because the two most recent readings are -3 and -10.

recordTemperature(temperature = -12)

getHighestRecentTemperature() returns -10 because the two most recent readings are -10 and -12.