You want to be able to access the largest element in a stack.
Use the built-inStackclass to implement a newclassMaxStack with a function getMax that returns the largest element in the stack.getMax should not remove the item.
Your stacks will contain only integers.
What if we push several items in increasing numeric order (like 1, 2, 3, 4...), so that there is a new max after each push? What if we then pop each of these items off, so that there is a new max after each pop? Your algorithm shouldn't pay a steep cost in these edge cases.
You should be able to get a runtime of for push, pop, and getMax.
We'll never post on your wall or message your friends.
Once you're logged in, you'll get free full access to this and 4 other questions.
time for push, pop, and getMax. additional space, where m is the number of operations performed on the stack.
Notice that our time-efficient approach takes some additional space, while a lazy approach (simply walking through the stack to find the max integer whenever getMax is called) took no additional space. We've traded some space efficiency for time efficiency.