Stack with find-min/find-max more efficient than O(n)?

This is a classic data structures question. The intuition behind the problem is as follows - the only way that the maximum and minimum can change is if you push a new value onto the stack or pop a new value off of the stack. Given this, suppose that at each level in the stack you keep track of the maximum and minimum values at or below that point in the stack. Then, when you push a new element onto the stack, you can easily (in O(1) time) compute the maximum and minimum value anywhere in the stack by comparing the new element you just pushed to the current maximum and minimum. Similarly, when you pop off an element, you will expose the element in the stack one step below the top, which already has the maximum and minimum values in the rest of the stack stored alongside it.

Visually, suppose that we have a stack and add the values 2, 7, 1, 8, 3, and 9, in that order. We start by pushing 2, and so we push 2 onto our stack. Since 2 is now the largest and smallest value in the stack as well, we record this:

 2  (max 2, min 2)

Now, let's push 7. Since 7 is greater than 2 (the current max), we end up with this:

 7  (max 7, min 2)
 2  (max 2, min 2)

Notice that right now we can read off the max and min of the stack by looking at the top of the stack and seeing that 7 is the max and 2 is the min. If we now push 1, we get

 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

Here, we know that 1 is the minimum, since we can compare 1 to the cached min value stored atop the stack (2). As an exercise, make sure you understand why after adding 8, 3, and 9, we get this:

 9  (max 9, min 1)
 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

Now, if we want to query the max and min, we can do so in O(1) by just reading off the stored max and min atop the stack (9 and 1, respectively).