双栈法的优化：压缩还原
方法一：简单的双栈法
在返回栈中的min值时，如果仅仅使用一个辅助变量min，则其值可能因为min元素被出栈而失效，常规的做法是额外添加一个同步栈（min栈），以保存记录之前所有的min值，相当于是使用了n个辅助变量，所以空间复杂度是O(n)。
但是，仅仅使用一两个辅助变量就真的不能达到目的了？？其实是可以的！我们考虑使用一种类似压缩的方法，来将数据栈和辅助栈合并成一个栈，因为经过分析可以发现，其实各个元素的值与最小值是有关联的，这之间存在着冗余的信息！
一个初步的优化是将min栈中因为没有新的min值入栈而产生的重复的min值舍弃掉，这一做法可以参考一叶浮尘的博客，但是在最坏情况下，它的辅助空间复杂度也是O(n)，即每次入栈的值都是更小值
方法二：压缩还原法
我们发现其实最小值min它本身就是一种冗余信息。为什么呢？因为每个元素在数值上都包含了min值，举个例子，假设入栈序列为：4、5、6、3、2、1，那么各轮次对应的min值就是：4、4、4、3、2、1，发现有：
4=4+0，5=4+1，6=4+2，3=4+(-1)，2=3+(-1)，1=2+(-1)；各个元素在数值上已经包含了在它之前的最小值的值；
那么，我们是不是只要在数据栈中存储0、1、2、-1、-1、-1，然后再使用一个辅助变量min=1就可以了呢？
这样，根据单个辅助变量和栈中存储的值就能够推理出top值和min值了，具体规则如下：
入栈：
- 压缩：将要入栈的元素value减去当前最小值min，得到一个差值diff，只存储该差值；
- 更新：如果入栈的元素value比当前最小值min小，则要更新最小值：min=value；
- 初始：第一次入栈比较特殊，因为此时的min变量并没有值，所以令：min=value；
出栈：
- 更新：如果栈中存储的差值diff是负数，说明出栈的元素是当前最小值min，需要把min值更新为上一个最小值min = min - diff，否则，出栈的元素不是最小值，则不对min变量做任何操作；
- 还原：如果栈中存储的差值diff是正数，说明 top = min + diff，否则，说明top元素本身是最小值 top = min；
致命的不足（2020.02.12）
非常感谢评论区里用户ThetaQing的提醒，她指出value-min的差值可能会发生溢出，比如一个是INT_MAX另一个是INT_MIN，这是一个致命的不足，这里找不到根本的解决方法，本来觉得使用python3可以缓解这个问题，后来觉得有点治标不治本，这个方法也因此变得没有应用价值了（想想阿丽亚娜5火箭爆炸事故，是吧），现在干脆就留着当反例好了。
当然，理论上这个想法还是OK的（理论与现实的差距）......同时这个故事还告诉我们：理论要联系实际，理论没有问题，可是计算机它的实际存储条件不支持咱也莫得法子......
故事之前（2019.08.25）
其实刚开始做这道题时，连引入最小栈这一做法都没想到，当时觉得很难，想了好久想到了Hash树（可以达到伪O(1)，实际上应该是log级的）...
下附实现代码，代码并不复杂：
class Solution {
stack<int> stack_;
int top_, min_;
public:
void push(int value) {
if (stack_.empty()) // 第一次入栈需要额外考虑
min_ = value;
stack_.push(value - min_); // 存储入栈元素与最小值的差值
if (value < min_) // 如果入栈元素比最小值要小则更新最小值
min_ = value;
top_ = value; //.......更新最新元素(top)的值
}
void pop() {
if (!stack_.empty()) {
// 如果出栈的是最小值(体现为存储值为负)，则需要更新最小值
if (stack_.top() < 0)
min_ -= stack_.top();
stack_.pop();
if (!stack_.empty()) // 出栈需要更新 top 的值
top_ = min_ + (stack_.top()>0 ? stack_.top() : 0);
}
}
int top() {
return top_;
}
int min() {
return min_;
}
};
京公网安备 11010502036488号