程序员面试金典03.05_go_栈排序
题目【程序员面试金典03.05_go_栈排序】栈排序 。编写程序 ， 对栈进行排序使最小元素位于栈顶 。
最多只能使用一个其他的临时栈存放数据 ， 但不得将元素复制到别的数据结构（如数组）中 。
该栈支持如下操作：push、pop、peek 和 isEmpty 。 当栈为空时 ， peek 返回 -1 。
示例1:输入：["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
输出：[null,null,null,1,null,2]
示例2:输入： ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
输出：[null,null,null,null,null,true]
说明:栈中的元素数目在[0, 5000]范围内 。
解题思路分析1、双栈；时间复杂度O(n) ， 空间复杂度O(n)
文章插图
type SortedStack struct { stack []int temp[]int}func Constructor() SortedStack { return SortedStack{}}func (this *SortedStack) Push(val int) { for len(this.stack) > 0 && val >= this.stack[len(this.stack)-1] {this.temp = append(this.temp, this.stack[len(this.stack)-1])this.stack = this.stack[:len(this.stack)-1] } this.stack = append(this.stack, val) for len(this.temp) > 0 {this.stack = append(this.stack, this.temp[len(this.temp)-1])this.temp = this.temp[:len(this.temp)-1] }}func (this *SortedStack) Pop() { if len(this.stack) == 0 {return } this.stack = this.stack[:len(this.stack)-1]}func (this *SortedStack) Peek() int { if len(this.stack) == 0 {return -1 } return this.stack[len(this.stack)-1]}func (this *SortedStack) IsEmpty() bool { return len(this.stack) == 0}总结Medium题目 ， 根据题目意思 ， 使用双栈 ， 核心是：push的时候 ， 借助辅助栈来插入数字
推荐阅读
- 程序员为教师妻子开发应用：将iPhone变成文档摄像头
- 悔哭！一程序员误把7500个比特币当垃圾扔掉，估算约2.4亿美元
- 2.4亿美元打水漂！程序员小哥把7500个比特币当垃圾扔掉 硬盘找不回
- 程序员开发抢茅台脚本：2天就刷榜Github
- 为什么我喜欢C语言，却非常讨厌C++？一位国外程序员的回答
- 程序员怎么保护头发？雷军回应
- 北美程序员Tinder翻车实录
- 导航|攻坚“卫星导航信号弱”难题，高德程序员联手武大学子夺得国际室内定位大赛冠军
- 长沙|视频｜聚焦“数字英雄”长沙银行冠名全国首档程序员电视真人秀
- 孙玲|从流水线女工逆袭成高薪程序员 一度爆红的她现在咋样了？