716.Max Stack | zhengxingxing

Method 1

Design a max stack data structure that supports the stack operations and supports finding the stack’s maximum element.
Implement the MaxStack class:
- MaxStack() Initializes the stack object.
- void push(int x) Pushes element x onto the stack.
- int pop() Removes the element on top of the stack and returns it.
- int top() Gets the element on the top of the stack without removing it.
- int peekMax() Retrieves the maximum element in the stack without removing it.
- int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

Example 1

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

Method 1

【O(log n) time | O(n) space】

package Leetcode.Stack;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

/**
 * @author zhengxingxing
 * @date 2024/11/10
 */
public class MaxStack {
    // Node class for doubly linked list
    private static class Node {
        int val;
        Node prev;
        Node next;
        Node(int val) {
            this.val = val;
        }
    }

    private Node head;  // Head node of doubly linked list
    private TreeMap<Integer, List<Node>> map;  // Map from value to nodes

    public MaxStack() {
        head = new Node(0);  // Sentinel node
        head.next = head.prev = head;
        map = new TreeMap<>();
    }

    public void push(int x) {
        Node node = new Node(x);
        // Insert new node at the head of linked list
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
        // Update TreeMap
        map.computeIfAbsent(x, k -> new ArrayList<>()).add(node);
    }

    public int pop() {
        Node node = head.next;  // Get top node
        // Remove node from linked list
        removeNode(node);
        // Remove node from TreeMap
        List<Node> nodes = map.get(node.val);
        nodes.remove(nodes.size() - 1);
        if (nodes.isEmpty()) {
            map.remove(node.val);
        }
        return node.val;
    }

    public int top() {
        return head.next.val;
    }

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

    public int popMax() {
        int maxVal = peekMax();
        List<Node> nodes = map.get(maxVal);
        Node node = nodes.remove(nodes.size() - 1);  // Remove the last (topmost) max value node
        if (nodes.isEmpty()) {
            map.remove(maxVal);
        }
        removeNode(node);  // Remove node from linked list
        return maxVal;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public static void main(String[] args) {
        // Create and execute test cases
        System.out.println("Start testing MaxStack:");

        // Test case 1: Example from the problem
        System.out.println("\nTest case 1 - Problem example:");
        MaxStack stk1 = new MaxStack();
        stk1.push(5);
        System.out.println("push(5)");
        stk1.push(1);
        System.out.println("push(1)");
        stk1.push(5);
        System.out.println("push(5)");
        System.out.println("top() = " + stk1.top());  // Expected output: 5
        System.out.println("popMax() = " + stk1.popMax());  // Expected output: 5
        System.out.println("top() = " + stk1.top());  // Expected output: 1
        System.out.println("peekMax() = " + stk1.peekMax());  // Expected output: 5
        System.out.println("pop() = " + stk1.pop());  // Expected output: 1
        System.out.println("top() = " + stk1.top());  // Expected output: 5

        // Test case 2: Testing duplicate elements
        System.out.println("\nTest case 2 - Duplicate elements:");
        MaxStack stk2 = new MaxStack();
        stk2.push(1);
        System.out.println("push(1)");
        stk2.push(1);
        System.out.println("push(1)");
        stk2.push(2);
        System.out.println("push(2)");
        System.out.println("popMax() = " + stk2.popMax());  // Expected output: 2
        System.out.println("top() = " + stk2.top());  // Expected output: 1
        System.out.println("peekMax() = " + stk2.peekMax());  // Expected output: 1

        // Test case 3: Testing continuous operations
        System.out.println("\nTest case 3 - Continuous operations:");
        MaxStack stk3 = new MaxStack();
        stk3.push(3);
        System.out.println("push(3)");
        stk3.push(2);
        System.out.println("push(2)");
        stk3.push(4);
        System.out.println("push(4)");
        System.out.println("peekMax() = " + stk3.peekMax());  // Expected output: 4
        System.out.println("pop() = " + stk3.pop());  // Expected output: 4
        System.out.println("top() = " + stk3.top());  // Expected output: 2
        System.out.println("peekMax() = " + stk3.peekMax());  // Expected output: 3
        System.out.println("popMax() = " + stk3.popMax());  // Expected output: 3
        System.out.println("top() = " + stk3.top());  // Expected output: 2
    }
}

Method 1

Enjoy Reading This Article?