手把手带你了解C++最小栈手把手带你了解C++最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

示例:

输入：
输出：
解释：

思路

总结

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。

pop() —— 删除栈顶的元素。

top() —— 获取栈顶元素。

getMin() —— 检索栈中的最小元素。
【手把手带你了解C++最小栈】
示例:

输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]

[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

思路
C++支持的栈（原生栈），可以实现 push、pop、top(peek)，但是要获取最小元素，一种方法是通过暴力搜索，从头到尾遍历整个，那么时间复杂度是 O(n)，不是在常数级获取最小值，不符合题目的要求。
我们可以设置两个栈，一个数据栈 datastack，用于存放需要存放的数据，一个记录最小值的栈 sortedstack。

文章图片

每次 push 操作之后，保存当前 push 元素之后数据栈中的最小值，因为从第一次 push 到之后的每次 push 操作，我们知道每次 push 的值，也很容易知道当前的栈中的最小值。

文章图片

```cppclass MinStack {public:/** initialize your data structure here. *///创建两个栈stack datastack; //数据栈stack sortedstack; //有序栈，栈底最大，栈顶最小，有<=栈顶的元素才pushMinStack() {}void push(int val) {datastack.push(val); //将值push到数据栈//有序栈//当有序栈为空或值小于等于有序栈的栈顶就pushif(sortedstack.empty()||val<=sortedstack.top()) //sortedstack==sortedstack.empty() 错误sortedstack.push(val); }void pop() {if(datastack.top()==sortedstack.top())//数据栈的栈顶和有序栈的栈顶相同，有序栈出栈sortedstack.pop(); datastack.pop(); //数据栈一直在出栈}int top() {return datastack.top(); }int getMin() {return sortedstack.top(); }}; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */

总结本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注脚本之家的更多内容！