题目: 设计包含 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 代码:
运行结果:
来源: https://juejin.im/post/5b76a69af265da2816596936