Deque is the right structure


  • 6
    S

    I tried three data structure: vector, list and deque. Only deque is accepted, the others got MLE.

    There are some explanation:

    A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.

    The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence. Additionally, deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.

    And my code:

    class MinStack {
    private:
        deque<int> st;
        deque<int> mi;
    public:
        void push(int x) {
            st.push_back(x);
            if (mi.empty() || x <= mi.back()) mi.push_back(x);
        }
    
        void pop() {
            if (st.empty()) return;
            if (st.back() == mi.back()) mi.pop_back();
            st.pop_back();
        }
    
        int top() {
            if (st.empty()) return -1;
            return st.back();
        }
    
        int getMin() {
            if (mi.empty()) return -1;
            return mi.back();
        }
    };

  • 0
    G

    Still it does not explain why List like ArrayList requires more memory?
    I am using Java. I failed with ArrayList, too. My second question is whether Deque in java supports random access?


  • 0
    M

    ArrayList is a dynamic array. It doubles the size when it reaches the capacity...


  • 0
    J

    Thanks. Still MLE with one-stack solution. LeetCode is making a big joke on me. :(


  • 0
    J

    I see others use five times the capacity and pass. It really sucks.


Log in to reply
 

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