定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数.要求时间复杂度是O(1)
定义两个栈,一个用来存储元素。另一个用来存储最小值。
minS[i]表示valueS从i到底的区间中最小值。
栈有先入后出的特性,也就是说,压入和弹出,从时间上来说,是镜像的。元素x压入时,栈的情形,和x弹出时栈的情形,是一样的。
所以说元素x压入时,栈的最小值,和x弹出时栈的最小值是一样的。
所以用minS栈来统计每个元素压入时(确切来说是压入后),valueS栈的最小值。
这样伴随着valueS中元素的逐个弹出,minS中元素也逐个弹出,来达到同步。
栈相当于是一个黑箱数组。我们只能看到栈顶,所以用栈做规划的话,需要在栈顶放“最”值。在这里,minS就是放最小值的,每一步骤数据栈内的最小值放入minS的栈顶。然后利用栈的镜像原理,达到快速求最小值的目的。
stack<int> valueS,minS;
void push(int value) {
valueS.push(value);
if(minS.empty())
minS.push(value);
else{
if(value<minS.top())
minS.push(value);
else
minS.push(minS.top());
}
}
void pop() {
valueS.pop();
minS.pop();
}
int top() {
return valueS.top();
}
int min() {
return minS.top();
}