C++的原生栈,可以实现 push、pop、top,但是要获取最小元素
一种方法是通过暴力搜索,从头到尾遍历整个,那么时间复杂度是 O(n),不是在常数级获取最小值, 不符合题目的要求。
所以我们可以设置两个栈,一个数据栈 st,用于存放需要存放的数据,一个记录最小值的栈 minst。
会影响当前最小值的操作只有两种一个是 push 一个是 pop
每次 push 时需要改变最小值的情况也有两种 :
①:当前栈为空,那push的元素一定是最小值
②:当前push的元素 ≤ minst的栈顶元素
每次pop时会改变最小值的情况只有一种
被删掉的正好是最小值:也就是st的栈顶元素 == minst的栈顶元素