O(1)时间复杂度的最小栈

1. Introduction

In this tutorial, we’ll show how to get the minimum element from a stack in time.

2. Problem Description

Design a number stack that supports regular stack operations of , , , and an additional operation which should return the minimum element from the stack.

Suppose we have 3 numbers . When we push the first number 5 into the stack, the stack top and minimum is 5:

When we push the number 6 into the stack, the stack top becomes 6, but the minimum is still 5:

When we push the number 3 into the stack, both the stack top and minimum become 3:

If we pop the top number 3, The minimum number is changed back to 5:

3. Two-stack Solution

We can use two stacks to construct the special minimum stack. The first stack, , stores all the elements. The second stack, , keeps track of the minimum numbers.

The top of the contains the top element of the stack. Also, we can access the minimum element from the top of the .

3.1. Two-stack Example

In our example, when we push the first number 5, we push it into both stacks:

When we push the number 6, the top of becomes 6. However, we don’t push it into because it is greater than the current minimum 5:

When we push the number 3, we push it into both stacks, as 3 is the new minimum number:

If we pop the number 3, we pop it from both stacks as 3 is the current minimum number:

3.2. Two-stack Algorithm

Based on the above example, we can use two stacks to implement , , and functions:

mainStack <- an empty stack
minStack <- an empty stack

function push(value):
    if mainStack.empty() or minStack.top() >= value:
        minStack.push(value)
        mainStack.push(value)

function pop():
    if mainStack.top() = minStack.top():
        minStack.pop()
        mainStack.pop()

function top():
    return mainStack.top()

function getMin():
    return minStack.top()

When we push a number, we also compare the number with the top of the . If the number is smaller than or equal to the current top of , we also push it into the . Similarly, we also compare the top numbers between and when we pop a number. If they are the same, we also pop the number from the .

In this algorithm, all operations take time. We use an extra stack to store the history of minimum numbers. Therefore, we need space for the function.

4. One-stack Solution

In order to get the minimum number in time, we need to keep the history of the minimum numbers. The two-stack solution uses an extra stack to achieve that. In the one-stack solution, we’ll track the history by a math calculation.

We use a single variable, , to store the current minimum value of the stack. If the stack is empty, we can push the number directly into the stack and set to the pushed number.

When we push a number, , into the non-empty stack, we first compare the number with the current minimum value, . If , we can push directly into the stack. The remains the same and the stack top value is the one we just pushed.

However, when we push a new minimum number, i.e., , we need to record this minimum value change at the stack position.

To record this minimum value change, we first need to differentiate this case with the case without the minimum value change, i.e., when . Therefore, we need to push a number that is less than the new minimum value into the stack. Also, we need to record the previous minimum value so that when we do operation, we can recover this number as the current minimum value.

4.1. One-stack Idea

Let the represent the number we push into the stack, represent the previous minimum value, which is before the operation, and represent the updated minimum value, which is . We can use the following formula to calculate :

Since is less than , we have . Therefore, . This means we push a number that is less than the new . In this way, we can know that this stack position indicates a change.

In this formula, we multiply with 2 so that is always less than . If we just use to calculate the , we’ll have a bigger for negative numbers.

For example, when we push a new minimum number -3 into the stack whose current minimum number is -2, we have

However, with the muplication of 2 on the , we have

When we do a operation, we compare the stack top with . If the stack top is less than , we can know that we made a minimum number change at this position. Therefore, we can return directly. Otherwise, we can just return the stack top as it is the real number, we pushed into the stack without the math transformation.

Similarly, when we do a operation, we first compare the stack top with . If the stack top is less than , we need to restore the to the previous one. We can calculate the previous minimum value by reversing the above formula:

4.2. One-stack Example

Based on the above example, we can use one stack and an extra variable to implement , , and functions:

mainStack <- an empty stack
minValue <- a variable to store the minimum value, initially contains the max possible value

function push(value):
    if mainStack.empty():
        mainStack.push(value)
        minValue = value
    else if value >= minValue:
        mainStack.push(value)
    else:
        mainStack.push(2 * value - minValue)
        minValue = value

function pop():
    if mainStack.top() < minValue:
        minValue = 2 * minStack.top() - minValue
    mainStack.pop()

function top():
    if mainStack.top() < minValue:
        return minValue
    else:
        return mainStack.top()

function getMin():
    return minValue

If we do operation at this time, we return the stack top value 6 as it is greater than the current .

When we push the number 3, we push the number into the stack. Also, we update the to be 3:

If we do operation at this time, we return , as the stack top value is less than .

If we do operation, we pop the stack top and update the to be :

4.3. One-stack Algorithm

Based on the above example, we can use one stack and an extra variable to implement , , and functions:

In this algorithm, all operations take time. Also, we use only one variable to store the minimum value. Therefore, we need space for the function.

5. Conclusion

In this article, we showed two solutions to design a minimum stack with time for regular stack operations and operation. With two stacks, we can achieve the design in a straightforward way. Also, we can reduce the memory requirement to by using some math transformation on the pushed numbers.