Assuming a set of numbers is given, we need to complete the minimum value of this set of numbers in O(1) time complexity Solve.
Specific description of the title: Define a stack, please implement a minimum value of the stack in this type The min function of the element. In this stack, call min,
The time complexity of push and push are both O(1) .
Two methods are given below:
Method 1: Use auxiliary stack implementation
Implementation process description: the auxiliary stack is specifically used to store the minimum value of the elements in the current data stack.
When the first element is pushed into the data stack, that element must also Auxiliary stack;
When an element is pushed into the data stack again, if the element is smaller than The top element in the auxiliary stack, push the element into the auxiliary stack;
Otherwise, that is, the newly pushed element is greater than the top element of the auxiliary stack, at this time, the top element of the auxiliary stack is pushed onto the stack again.
The implementation code is given below:
#includeusing namespace std;template class Stack{public: Stack() :_data(NULL) ,_min(NULL) ,_size(0) ,_capacity(0) {} ~Stack() {delete[] _data; delete [] _min; _data = NULL; _min = NULL; _size = 0; _capacity = 0;} void Push(const T& x) {CheckCapacity(); _data[_size] = x; //++_size; if (x < _min[_size-1] || _size == 0) {_min[_size] = x;} else {_min[_size] = _min[_size-1];} ++_size;} void Pop() {if (_size > 0) {--_size;}} size_t Min() {return _min[_size-1]; }protected: void CheckCapacity() {if (_size >= _capacity) {size_t NewCapacity = 2 * _capacity + 5; T* tmp1 = new T[NewCapacity]; T* tmp2 = new T[NewCapacity]; //copy content for (size_t i = 0; i <_size; ++i) {tm p1[i] = _data[i];} delete[] _data; _data = tmp1; for (size_t i = 0; i <_size; ++i) {tmp2[i] = _min[i];} delete[] _min; _min = tmp2; _capacity = NewCapacity;} }private: T* _data; T* _min; size_t _size; size_t _capacity;};void test(){ Stack s; s.Push(3); s. Push(4); s.Push(2); s.Push(1); cout << s.Min() << endl; s.Push(0); cout << s.Min() << endl; }int main(){ test(); system("pause"); return 0;}
Of course, in fact, we don’t need to save multiple copies of the minimum value~~ This is probably a little harder to control when implemented~ Both stacks need to have their own size and
capacity, this can be achieved by yourself.
Method 2: Push smaller elements into the stack twice
< p>implementation process: start to push the first element into the stack twice.
After that, if an element is smaller than The top element of the stack is pushed twice; if it is larger than the top element of the stack, the new element is placed below the top element of the stack (take out the top element of the stack
Plain, put the new element, and finally put it into the top element of the original stack)< /p>
The implementation code is given below:
#includeusing namespace std;# include template class Stack{public: Stack(T arr[], int size) :_arr(arr), _size(size) {} T Min() {int i = 0; stack s; s.push(_arr[0]); s.push(_arr[0]); for (i = 1; i <_size; ++i) {if ((s.empty()) || (s .top()> _arr[i])) {s.push(_arr[i]); s.push(_arr[i]);} else {int min = s.top(); s.pop(); s.push(_arr[i]); s.push(min);}} return s.top();} T& Top() {return _arr[_size -1]; }private: T* _arr; int _size;};void test(){ int arr[7] = {2,3,1,4,5,0,-3 }; Stack Arr( arr, 7); cout << Arr.Min() << endl;}int main(){ test(); return 0;}
This method is relatively simple to implement, but the stack is static. It might be good if it is implemented dynamically~~ However, the first method is already I have implemented the dynamics
state stack, it won’t be given here~~~