# 716. Max Stack

Reference: LeetCode
Difficulty: Easy

## Problem

Design a max stack that supports push, pop, top, peekMax and popMax.

Note:

• -1e7 <= x <= 1e7
• Number of operations won’t exceed 10000.
• The last four operations won’t be called when stack is empty.

Example:

## Analysis

My first attempt (ListNode): gist Not Accepted

Failed in case: [3 5 1] (popMax 5, it does not know the max is then 3).

However, by writing the code I improved writing functions in ListNode.

### Two Stacks (as in 155. Min Stack)

This solution is based on the brute-force solution in 155. Min Stack.

Time: pop() and popMax() take $O(N)$
Space: $O(N)$

### Two Stacks

Note:

The following popMax() is not correct. Why? Use stack.pop() or pop()? Or use which push()?

Time: Only popMax() takes $O(N)$
Space: $O(N)$

The optimization can be made in finding the largest element by TreeMap.

Nice Intuition:

Comment
Junhao Wang
a software engineering cat
Newest Comments
loading...
Info
Article :
50
Total Count :
82.4k
UV :
PV :
Last Push :