描述

这是一篇面对初级coder的题解。
知识点：栈
难度：二星

题解

题目：
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素

这道题考察栈的知识：
本题难点是如何维护最小元素，如果用一个单一值来记录最小值，
最小值出栈后就会用O(n)复杂度重新查找，最坏情况时间复杂度O(n)，不符合题目要求

双栈法

可以采用一个最小元素的栈来维护这样一个数据结构 



#include <stack>
class Solution {
    stack<int> data,mindata;//双栈法，维护一个数据栈和一个最小值栈
public:
    void push(int value) {
        data.push(value);//数据栈入栈
        if(mindata.size()==0||value<=mindata.top())//如果入栈值小于等于最小值，或当前栈为空
            mindata.push(value);//，最小值栈入栈
    }
    void pop() {
        if(mindata.top()==data.top())//如果出栈是当前的最小值
            mindata.pop();//最小值栈出栈
        data.pop();//数据栈出栈
    }
    int top() {
        return data.top();//返回数据栈栈顶元素
    }
    int min() {
        return mindata.top();//返回最小值栈栈栈顶元素
    }
};                   
  • 时间复杂度: O(1)
  • 空间复杂度: O(n)，最坏情况要保存全部值。
  • 运行时间7ms  占用内存620KB

残差法

能否在时间复杂度不变的前提下，进一步缩小空间复杂度？
可以在栈中只记录与最小值的差，
那么就存在一个问题，随着元素的输入，mindata的值是在变化的 每次push()入栈一个更小的元素都需要把stack中的差更新一遍吗?
答案是不需要。
试想，当我们引入一个更小的元素value时，它与mindata的差dis = x - mindata显然是个负数，那么这时就要更新mindata=value
那么如果value要出栈的话，stack中保存的是value进栈之前与上一个mindata的差，这时只要将mindata= mindata-value就可以将mindata回退到value入栈之前的最小值。

栈中值为负数的时候 top 和pop都需要特殊判断
#includeclass Solution {
    stackdata;//残差法，维护一个数据栈（记录每个元素与最小值差）
    int mindata;//和一个最小值
public:
    void push(int value) {
        if(data.size()==0)//如果当前栈为空
            mindata=value;//更新当前最小值
        data.push(value-mindata);//数据栈入栈
        if(value-mindata<0)//入栈值小于等于最小值 mindata=value;//更新当前最小值 } void pop() { if(0>=data.top())//如果出栈是当前的最小值 
            mindata=mindata-data.top();//最小值更新
        data.pop();//数据栈出栈
    }
    int top() {
        if(0>=data.top())//如果出栈是当前的最小值 
            return mindata;//返回最小值
        else
            return mindata+data.top();//返回数据栈栈顶元素
    }
    int min() {
        return mindata;//返回最小值
    }
};
  • 时间复杂度: O(1)
  • 空间复杂度: O(1),只需要一个额外的空间维护mindata即可。
  • 运行时间3ms 占用内存492KB

总结

栈的特点是后进先出 前面的数据在后面的数据处理完之前无需更改
需要利用栈的特性