Why does the C++ implementation meets Memory Limit Exceeded while the JAVA passes the test?


  • 0

    Hi, I write the following code that uses only one stack in C++ but it meets the "Memory Limit Exceeded" problem during the test. The code is as follows:

    class MinStack { 
    public:
        void push(int x) {
            if(data.empty()) {
                data.push(0L);
                minVal = x;
                return;
            }
            data.push(x - minVal);
            if(x < minVal) minVal = x;
        }
    
        void pop() {
            if(data.empty()) return;
            if(data.top() < 0) minVal -= data.top();
            data.pop();
        }
    
        int top() {
            if(data.top() > 0) return (int)(data.top() + minVal);
            else return (int)minVal;
        }
    
        int getMin() {
            return (int)minVal;
        }
    private:
        stack<long> data;
        long minVal;
    };
    

    However, another JAVA implementation (taken from http://blog.csdn.net/u010367506/article/details/41045797) of the same algorithm passes the test. The JAVA version is as follows:

    public class MinStack {
        public MinStack(){
            stack=new Stack<>();
        }
    
        public void push(int x) {
            if (stack.isEmpty()){
                stack.push(0L);
                min=x;
                return;
            }
            stack.push(x-min);//Could be negative if min value needs to change
            if (x<min) min=x;
        }
    
        public void pop() {
            if (stack.isEmpty()) return;
    
            long pop=stack.pop();
    
            if (pop<0)  min=min-pop;//If negative, increase the min value
    
        }
    
        public int top() {
            long top=stack.peek();
            if (top>0){
                return (int)(top+min);
            }else{
               return (int)(min);
            }
        }
    
        public int getMin() {
            return (int)min;
        }
    
        long min;
        Stack<Long> stack;
    }
    

    Well, I do not see some key differences above. Could anyone help me figure the problem out? Thank you.


  • 1
    V

    C++'s stack (unless you specify a container class) is backed by a deque, which is implemented with a vector of vector. This means much more allocation overhead.

    Try replacing it with std::vector (or use instantiate std::stack<T, std::vector>).


  • 0

    Hi, viktor3. Thank you for your answer. Since I am still not quite familiar with instantiate, I try std::vector ad the revised code is as follows. However, the Memory Limit Exceeded problem still appears.

    class MinStack { 
    public:
        void push(int x) {
            if(data.empty()) {
                data.push_back(0L);
                minVal = x;
                return;
            }
            data.push_back(x - minVal);
            if(x < minVal) minVal = x;
        }
    
        void pop() {
            if(data.empty()) return;
            if(data.back() < 0) minVal -= data.back();
            data.pop_back();
        }
    
        int top() {
            if(data.back() > 0) return (int)(data.back() + minVal);
            else return (int)minVal;
        }
    
        int getMin() {
            return (int)minVal;
        }
    private:
        vector<long> data;
        long minVal;
    };

Log in to reply
 

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