/ fun

Interview Practice 02 - Stack with Minimum Function

Question

Define a stack structure with “min” function — a function to get the minimum value within the stack. The time complexity of min, push and pop functions must be O(1).

Solution

0: 10 -> NULL (MIN=10, POS=0) 1: 7 -> [0] (MIN=7, POS=1) // 用數組表示堆棧，第0個元素表示棧底 2: 3 -> [1] (MIN=3, POS=2) 3: 3 -> [2] (MIN=3, POS=3) 4: 8 -> NULL (MIN=3, POS=3) // 技巧在這裡，因為8比當前的MIN大，所以彈出8不會影響當前的MIN 5: 5 -> NULL (MIN=3, POS=3) 6: 2 -> [2] (MIN=2, POS=6) // 如果2出棧了，那麼3就是MIN 7: 6 -> [6]

Samples

The following is an optimized implementation.  Repeated minimum value will not be stored through comparing values while pushing or popping values.

include #include using namespace std; /** * Class defining a new type of stack supporting any datatype. / template class StackWithMin { private: vector dataStack; // stacks to store data vector<size_t> minStack; // stack to store position of minimum value public: /* * Push data to the stack at the same time update the minimum stack if the * new data is smaller then the current minimum value. Throw exception if * stack is empty. / void push(T data) { dataStack.push_back(data); if (minStack.empty() || data < dataStack[minStack.back()]) minStack.push_back(dataStack.size()-1); } /* * Pop data to the stack at the same time pop from the min stack if it is * popping the minimum value. Throw exception if stack is empty. / void pop() { assert(!dataStack.empty()); if (dataStack.back() == dataStack[minStack.back()]) minStack.pop_back(); dataStack.pop_back(); } /* * return the current minimum value. / T min() { assert(!dataStack.empty() && !minStack.empty()); return dataStack[minStack.back()]; } }; /* * Main program */ int main() { StackWithMin stack = StackWithMin(); stack.push(10); stack.push(7); stack.push(3); stack.push(3); stack.push(8); stack.push(5); stack.push(2); stack.push(6); printf("Minimum value: %dn", stack.min()); }

import java.util.Stack; public class Pactice02 { public static void main(String[] args) { System.out.println("Hello World!"); AdvancedStack stack = new AdvancedStack(); stack.push(10); stack.push(7); stack.push(3); stack.push(3); stack.push(8); stack.push(5); stack.push(2); stack.push(6); System.out.println("Minimum value: "+ stack.getMinimum()); stack.pop(); System.out.println("Minimum value: "+ stack.getMinimum()); stack.pop(); System.out.println("Minimum value: "+ stack.getMinimum()); stack.pop(); System.out.println("Minimum value: "+ stack.getMinimum()); } public static class AdvancedStack extends Stack { private Stack mMinimumStack = new Stack(); @Override public E push(E item) { if (mMinimumStack.empty() || item.doubleValue() 0) { return mMinimumStack.peek(); } return null; } } }