Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Max Stack

Posted on February 12, 2018July 26, 2020 by braindenny

Max Stack



Similar Problems:

  • LeetCode: Min Stack
  • LeetCode: Maximum Frequency Stack
  • Insert Delete GetRandom O(1) – Duplicates allowed
  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #oodesign, #stack, #designstack

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

  1. push(x) — Push element x onto stack.
  2. pop() — Remove the element on top of the stack and return it.
  3. top() — Get the element on the top.
  4. peekMax() — Retrieve the maximum element in the stack.
  5. popMax() — Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Example 1:

MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5

Note:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/max-stack
## Basic Ideas: 2 stacks
##
## Complexity: Time: topMax O(n), others O(1)
##             Space: O(1)
class MaxStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.maxStack = []

    def pushHelper(self, x):
        self.stack.append(x)
        max_v = x
        if len(self.maxStack) != 0 and self.maxStack[-1] > max_v:
            max_v = self.maxStack[-1]
        self.maxStack.append(max_v)

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.pushHelper(x)


    def pop(self):
        """
        :rtype: int
        """
        self.maxStack.pop()
        return self.stack.pop()


    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]


    def peekMax(self):
        """
        :rtype: int
        """
        return self.maxStack[-1]


    def popMax(self):
        """
        :rtype: int
        """
        max_v = self.maxStack[-1]
        tmpStack = []
        while self.stack[-1] != max_v:
            tmpStack.append(self.stack.pop())
            self.maxStack.pop()
        self.stack.pop()
        self.maxStack.pop()
        while len(tmpStack) != 0:
            self.pushHelper(tmpStack.pop())
        return max_v

# Your MaxStack object will be instantiated and called as such:
# obj = MaxStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.peekMax()
# param_5 = obj.popMax()
linkedin
github
slack

Post Views: 3
Posted in MediumTagged #stack, designstack, oodesign

Post navigation

LeetCode: Design Hit Counter
LeetCode: Design Phone Directory

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.