Wednesday, August 05, 2015

min() and max() for stack in O(1)

//example
1    1   -
1    1   -
6    -   6
6    -   6
5    5   5
main min max
stack:
    main = new stack()
    min = new stack()
    max = new stack()
    
    push(x):
        main.push(x)
        if min.isempty() || x <= min.peek():
            min.push(x)
        if max.isempty() || x >= max.peek():
            max.push(x)
    
    x pop():
        if main.isempty():
            throw
        x = main.pop()
        if x == min.peek():
            min.pop() //ignore
        if x == max.peek():
            max.pop() //ignore
        return x
    
    // time: O(1), space: O(n)
    x min():
        if min.isempty():
            throw
        return min.peek()
    
    // time: O(1), space: O(n)
    x max():
        if max.isempty():
            throw
        return max.peek()

No comments:

Post a Comment