剑指 Offer 30. 包含min函数的栈

难度：简单

成都创新互联公司是专业的汾西网站建设公司，汾西接单;提供网站制作、网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行汾西网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

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

minStack.pop();

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

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

提示：

各函数的调用总次数不超过 20000 次

思路：

应用辅助栈的思路。这个辅助栈的用途就是与原来的栈同步地进行插入与删除，存储与每个元素对应的最小值。定义原来的栈为stack1,辅助栈为stack2。

stackstack1;
 stackstack2;

同样地，力扣的oj已经给出了代码的结构。我们需分别补充MinStack(),push(),pop(),top()和min()。

1. MinStack()

MinStack() {
        stack2.push(INT_MAX);//为什么这里要先压入一个INT_MAX? 因为每次push操作时stack2中要插入的值 = min(当前要push的值, 即stack2的栈顶值)，第一次push时stack2是空的,栈顶值为null，如果先压一个INT_MAX就可以解决这个问题，否则需要写if判断这种情况。
    }

2. push()

当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；

void push(int x) {
        stack1.push(x);
        stack2.push(::min(stack2.top(), x));//这里：：min的意思是全局作用域符号，当全局变量在局部函数中与其中某个变量重名，就可以用：：来区分
    }

3. pop()

当一个元素要出原栈时，我们把辅助栈的栈顶元素也一并弹出；

void pop() {
        stack1.pop();
        stack2.pop();
    }

4. top()和min()

top()返回的是原栈的栈顶元素，栈内元素的最小值存储在辅助栈的栈顶元素中。这样一来，每次入栈都会维护一次最小值，无需在最后一步遍历整个栈寻找最小值，大大节约了时间。

int top() {
        return stack1.top();
    }

int min() {
        return stack2.top();
    }

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站题目：力扣刷题day2-创新互联
转载源于：http://kswjz.com/article/ccosee.html