设计包含min函数的栈

题目：设计包含min函数的栈

原创： 白话算法

要求：定义一个栈的数据结构，要求添加一个min函数，使他能够找到栈的最小元素。

要求是：函数min push pop的时间复杂度都是o(1)

写在前面：为什么会有写这样一个公众号的想法呢？我的工作的是测试开发，在工作中大多是写一些工程类的代码，对算法类的代码写的比较少，因为想提高算法的思路，同时又想保持写代码的基本能力，所以想到了写公众号的办法，也希望看到文章的同学们，大家可以一起进步~ 本题目是在网上找的goole的一道面试题；一开始的想法是用一个int类型存储数组中的最小值，但是这样有pop或者有push操作时，一旦数据变了，就获取不到栈中的最小值了。

所以代码思路：用一个单独的数组存贮数A之前最小值的下标

比如数据是 20, 0, -1, -2, 9, 10,100,-90，

那么最小值小标为 0，1，2，3，3，3，3，7

代码中有几个注意点：

1 对于输入的限制为数字

2 出栈时判断栈是否为空

3 存贮最小值下标是，是存这个数之前最小值的下标，写的时候容易误写成，存储前一个数的下标，建议多用几组数据进行测试

比如： 0，1，2，3，4； 4，3，2，1 2，3，-1，0，-90，100 20, 0, -1, -2, 9, 10,100,-90

php代码：

image image

运行结果：

image

如果大家有更好的算法，欢迎沟通交流 也欢迎大家用其他语言实现

更多内容，欢迎关注微信订阅号“玄魂工作室”

点击打开二维码