716. Max Stack

• 716. Max Stack
  • Description
  • Intuition
  • Pitfall
  • Solution
  • Reference

Description

Here

Intuition

We cannot get all operations to O(1).

Either push(x) or popMax() needs to be Log(N).

Remeber

1. If we need push(x) more efficient, we can have 2 stacks, one of which stores the value while the other stores the max value.
2. If we need popMax() more effcient, we need create have a map which maps from key to a LinkedList, and a normal double linked list.

Pitfall

Solution

PopMax() is O(1)

push() O(1)

Reference

Prove No O(1) Solution-isn't-possible)