算法|寻找不规律栈中最小元素

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

在之前的课程中，我们学习到了栈的知识。栈中的元素不可能都是像例题描述的一样规规矩矩的按顺序储存在栈中，在实际运用中，栈中的元素往往是杂乱、没有顺序的。出于实际的考虑，就需要我们去准确的定位栈中的元素。在本文章中，我们来探究探究怎么准确的定位栈中最小元素。

在遇到寻找特定元素的问题时，很多人就会说，来设计个算法不就能解决了吗？何必还有深思其他方法去寻找。可当我们加上时间复杂度来思考后呢？不难发现鲜有排序和查找能够在很短的时间内解决这个问题。

既然是一个栈不能解决的问题，我们何不再找个它的兄弟来帮忙。兄弟齐心，其利断金嘛。所以，我们试试看，双栈能不能解决这个问题。

我们都了解元素进出栈的规律，所以我们选择两个栈，其中一个用来储存数据，另外一个用来储存最小值。

我们可以发现，栈A中的元素是不规律的，入栈顺序是7、8、9、6、10，那么元素的出栈顺序就是10、6、9、8、7，在数据很少的情况下我们可以看出在栈A中要寻找的最小元素是6，但是在寻找之前我们并不知道栈A中的最小元素是何值,所以我们在另外一个栈中先任意储存一个值X。接下来，我们通过不断地push和pop操作来保持栈B中的栈顶元素一直为最小值。

• 入栈

当有大于或等于X的值入栈A时，我们保持X为最小值不变，并将新元素压如栈A；当有小于X的值Y入栈A时，我们改变现在的最小值为Y,并将元素Y同时压入栈A和栈B。图示为当Y