C++ using linked list.


  • 0
    N
    #include <stdlib.h>
    
    class MinStack {
    public:
        /** initialize your data structure here. */
        MinStack() {
            
        }
        
        ~MinStack() {
            while (nullptr != topNode) {
                Node* next = topNode->next;
                free(topNode);
                topNode = next;
            }
            topNode = nullptr;
            minNode = nullptr;
        }
        
        void push(int x) {
            _push(x);
            if (_isFirstPush() || getMin() > x) {
                topNode->nextMin = minNode;
                minNode = topNode;
            }
        }
        
        void pop() {
            assert(nullptr != topNode);
            Node* aNode = _pop();
            if (minNode == aNode) {
                minNode = minNode->nextMin;
            }
            free(aNode);
            aNode = nullptr;
        }
        
        int top() {
            assert(nullptr != topNode);
            return topNode->value;
        }
        
        int getMin() {
            assert(nullptr != minNode);
            return minNode->value;
        }
        
    private:
        
        typedef struct _Node {
            int value;
            _Node* next;
            _Node* nextMin;
        } Node;
        
        Node* minNode = nullptr;
        
        Node* topNode = nullptr;
        
        void _push(int x) {
            Node* aNode = (Node*)malloc(sizeof(Node));
            aNode->value = x;
            aNode->next = topNode;
            topNode = aNode;
        }
        
        Node* _pop() {
            Node* aNode = topNode;
            topNode = topNode->next;
            return aNode;
        }
        
        bool _isFirstPush() {
            return nullptr == topNode->next;
        }
    };
    

    Used an additional pointer to keep track of minimum node.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.