无为清净楼资源网 Design By www.qnjia.com
前言
遇到一道面试题,题目大概意思如下:
使用两个普通栈实现一个特殊栈,使得pop、push、min三个函数的都是复杂度为O(1)的操作,min函数是获得当前栈的最小值。
初步想法
1.要实现min函数为(1)操作,当时第一想法是事先需要算好当前最小值,于是会想到用一个值来保存当前栈中最小值元素,然后push和pop操作的时候维护这个值。这样min,push都是O(1)了,但pop可不是,如果当前弹出的是最小值,需要从新寻找当前元素的最小值,这个就不是o(1)了。
2.而且上面方法没有用到另外一个栈,于是又想到:在一个栈中存储排好序的元素,同样在push和pop操作中维护这个有序堆栈,如图:
但是这样的话min操作是O(1),但是push、pop操作因为要维护这个有序栈,怎么也想不到一个方法可以O(1)的复杂度。
当时觉得肯定是在另一个栈中缓存最小值信息,但是不知道是因为没吃饭还是怎么地,思维就此僵住了。
正确解法
遇到问题解决不了,感觉心里很不爽,于是吃饭的时候又开始想怎么充分理由栈的特性,有效的缓存最小值信息,以便min操作使用。
栈操作最大的特性是只能操作栈顶元素,想到那用一个辅助栈缓存每次栈操作时的最小值,不是刚刚好。这样每次pop操作的时候,两边一起弹出就可以;因为辅助栈的栈顶元素最当前栈中的最小值,push操作是也只需要比较入栈元素和辅助栈栈顶元素就可以。这样push、pop、min都都O(1)操作了。如图:
文字可能没说清楚,上代码,下面是PHP的实现,通过数组来模拟堆栈。
<"codetitle">复制代码 代码如下:
$obj = new strack();
$obj->push(12);
$obj->push(56);
$obj->push(23);
$obj->push(89);
$obj->push(4);
var_dump($obj->min());
$obj->pop();
var_dump($obj->min());
$obj->push(8);
var_dump($obj->min());输出为:
复制代码 代码如下:
int(4)
int(12)
int(8)OK,满足要求。
你是否有其他更好方法实现,如果有,请告诉我^_^
标签:
PHP,栈,面试题
无为清净楼资源网 Design By www.qnjia.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
无为清净楼资源网 Design By www.qnjia.com
暂无评论...
更新日志
2024年09月23日
2024年09月23日
- 黑鸭子.2005-《发烧DSD》柏菲[WAV分轨]
- 群星.1990-电影看板·人间道【宝丽金】【WAV+CUE】
- 周殷廷.2024-TO.WHOM.IT.MAY.CONCERN【环球】【FLAC分轨】
- 草蜢.1997-三人世界精选17首【宝丽金】【WAV+CUE】
- 【古琴音乐】管平湖《广陵散》2004[FLAC+CUE]
- 【中国民乐】《少数民族器乐·苗岭的早晨》2004[WAV+CUE]
- 【中国音乐】盛中国《新疆之春》2004[FLAC+CUE]
- 群星《音你而来 第8期》[320K/MP3][44.64MB]
- 群星《音你而来 第8期》[FLAC/分轨][121.21MB]
- 群星《十二女声Ⅲ》[WAV/CUE/分轨][626.4MB]
- 陈百强.1993-离不开...纪念歌集2CD【华纳】【WAV+CUE】
- 于台烟.2003-爱自己【乾坤唱片】【WAV+CUE】
- 群星.2024-我们永远是我们电影原声带【乐禾发文化】【FLAC分轨】
- 【中国民乐】张维良《秋江夜泊》2004[FLAC+CUE]
- 明达年度发烧碟MasterSuperiorAudiophile2011[DSF]