D
DevExCode

LeetCode 716: Max Stack Solution

Master LeetCode problem 716 (Max Stack), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

The Max Stack problem requires us to design a data structure that supports the following operations efficiently:

  1. push(x): Add element x to the top of the stack.
  2. pop(): Remove and return the top element of the stack.
  3. top(): Return the top element of the stack.
  4. peekMax(): Return the maximum element in the stack.
  5. popMax(): Remove and return the maximum element in the stack.

To solve this problem efficiently, we can use a combination of a stack and a priority queue (or a sorted list). By maintaining a stack for the elements and a priority queue to keep track of the maximum element, we can achieve the required operations in logarithmic time complexity.

Here's a high-level outline of the algorithm:

  1. Use a stack to store the elements of the stack.
  2. Use a priority queue to store the elements in sorted order for efficient retrieval of the maximum element.
  3. Implement the required operations by updating both the stack and the priority queue as necessary.

Time Complexity:

  • push(x): O(log n)
  • pop(): O(log n)
  • top(): O(1)
  • peekMax(): O(1)
  • popMax(): O(n)

Space Complexity:

O(n)

: :

Solution Code

import java.util.Stack;
import java.util.TreeMap;

class MaxStack {
    Stack<Integer> stack;
    TreeMap<Integer, Integer> maxMap;

    public MaxStack() {
        stack = new Stack<>();
        maxMap = new TreeMap<>();
    }

    public void push(int x) {
        stack.push(x);
        maxMap.put(x, maxMap.getOrDefault(x, 0) + 1);
    }

    public int pop() {
        int top = stack.pop();
        if (maxMap.get(top) == 1) {
            maxMap.remove(top);
        } else {
            maxMap.put(top, maxMap.get(top) - 1);
        }
        return top;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return maxMap.lastKey();
    }

    public int popMax() {
        int max = maxMap.lastKey();
        if (maxMap.get(max) == 1) {
            maxMap.remove(max);
        } else {
            maxMap.put(max, maxMap.get(max) - 1);
        }
        Stack<Integer> temp = new Stack<>();
        while (stack.peek() != max) {
            temp.push(stack.pop());
        }
        stack.pop();
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
        return max;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 716 (Max Stack)?

This page provides optimized solutions for LeetCode problem 716 (Max Stack) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 716 (Max Stack)?

The time complexity for LeetCode 716 (Max Stack) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 716 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 716 in Java, C++, or Python.

Back to LeetCode Solutions