/ 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

結合鍊錶一起做。首先我做插入以下數字: 10, 7, 3, 3, 8, 5, 2, 6

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]

出棧的話採用類似方法修正。

所以,藉助輔助棧,保存最小值,且隨時更新輔助棧中的元素。push第一個元素進A,也把它push進B,當向Apush的元素比B中的元素小, 則也push進B,即更新B。否則,不動B,保存原值。向棧A push元素時,順序由下至上。輔助棧B中,始終保存著最小的元素。

然後,當pop A中的元素小於B中棧頂元素時,則也要pop B中棧頂元素。

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; } } }