Max Stack

Design a stack data structure that supports standard push, pop, and top operations, along with a getMax operation that retrieves (but does not remove) the maximum element in O(1) time. The core challenge is maintaining the current maximum efficiently across arbitrary pushes and pops without requiring removal of the maximum from an arbitrary position.