Share my codes & the answer given by the system(leetcode OJ) is not so good when two or more same numbers are pushed.


  • 1
    Q

    the answer given by the system(leetcode OJ) could be like this:
    dataStack{5,4,3,3,3,3,3,...,3,3,2} (push data from the left hand to the right hand)
    MinStack {5,4,3,3,3,3,3,....3,3,2}
    It is not so good.
    However, my code would be like this:
    MinStack{5,4,3,2} with a counter for every data in the MinStack.
    In fact, only when there's little or a little two or more same numbers, the codes gived by leetcode OJ are best.
    Here's my codes:

    class MinStack {
        
        public:
        struct NODE{
                int val;
                int cnt;
            };
        
            stack<NODE> s_min;
            stack<int> s_data;
            void push(int x) {
                s_data.push(x);
                if(s_min.empty()||x<s_min.top().val)
                {
                    NODE node;
                    node.val=x;
                    node.cnt=1;
                    s_min.push(node);
                }
                else
                {
                    NODE node=s_min.top();
                    s_min.pop();
                    node.cnt++;
                    s_min.push(node);
                }
                
            }
        
            void pop() {
                NODE node=s_min.top();
                s_min.pop();
                node.cnt--;
                if(node.cnt>0)
                  s_min.push(node);
                s_data.pop();
                
                
            }
        
            int top() {
                return s_data.top();
            }
        
            int getMin() {
                return s_min.top().val;
            }
           
        };

  • 0
    S

    Do you mean missing test case? Can you provide it which will fail this AC solution?


  • 0
    Q

    dataStack{5,4,3,3,2}
    MinStack{5,4,3,2}
    when the first 3 is pop in the dataStack, the 3 is also pop in the MinStack.
    The second 3 in the dataStack doesn't match the 4 in the mInStack.


  • 0
    S

    How could it be possible to have dataStack and minStack like that? Can you provide a action list? Say push 5, push 4 ...


  • 0
    S

    Guess you misunderstand the algorithm, only for those "bigger" than the current top minimum in the minStack, we can ignore them (means we do not need to put it in the minStack), for those equal to the current top minimum (the second 3 in your example), we still need to put it into the minStack, so the minStack should look like {5, 4, 3, 3, 2}, does that make any sense? feel free to let me know if it is still unclear~


  • 0
    Q

    You are right. I misunderstood part of the algorithm. However, the algorithm is still not so good when the same two or more numbers were pushed. So I have to change my title.


  • 0
    Q

    Sorry for my misunderstanding part of the algorithm. Look at my whiteboard.I have changed some.


  • 0
    S

    Great JOB! But It really depends on specific cases, in your cases, yours is better
    but in cases like element stack is {5, 4, 3, 2, 1} and minStack is
    {5, 4, 3, 2 , 1} your approach cost n (n = 5 here) more space


  • 0
    Q

    Yes, no algorithm is perfect.


Log in to reply
 

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