LintCode 229 [Stack Sorting]

原题

请设计一种方法将一个栈进行升序排列 (最大的数在最上面)。

你可以使用另外一个栈来辅助操作,但不可将这些数复制到另外一个数据结构中 (如,数组)。

样例
给一个栈:

| |
|3|
|1|
|2|
|4|
 -

排序之后:

| |
|4|
|3|
|2|
|1|
 -

栈会被序列化为[4,2,1,3],也就是说最右边是栈顶。

解题思路

  • 首先,把所有元素从原stack倒进临时stack,然后每次从临时stack拿出一个元素放入current中:
  • 若该current大于原stack中最上面的元素,则直接加入原stack
  • 若该current小于原stack中的元素,就把原stack中的元素放回临时stack,直到原stack顶上的元素小于current或者原stack为空,则将current放入原stack
  • 从而,保证了原stack中的元素从底到上是按有小到大排序的

完整代码

#Your can use Stack class in your solution.
#class Stack:
#  def __init__(self, stk=[])
#    # use stk to initialize the stack
#  def isEmpty(self)
#    # return true is stack is empty or false/
#  def push(self, item)
#    # push a element into stack and return nothing
#  def pop(self)
#    # pop a element from stack
#  def peek(self):
#    # return the top element if stack is not empty or nothing
#  def size(self):
#    # return the size of stack
class Solution:
    # @param {Stack} stk an integer Stack
    # @return {int} void
    def stackSorting(self, stk):
        # Write your code here
        tempStk = Stack()
        while not stk.isEmpty():
            tempStk.push(stk.pop())

        while not tempStk.isEmpty():
            current = tempStk.pop()
            while not stk.isEmpty() and stk.peek() > current:
                tempStk.push(stk.peek())
                stk.pop()
            stk.push(current)
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,173评论 0 12
  • 从三月份找实习到现在,面了一些公司,挂了不少,但最终还是拿到小米、百度、阿里、京东、新浪、CVTE、乐视家的研发岗...
    时芥蓝阅读 42,376评论 11 349
  • Java8张图 11、字符串不变性 12、equals()方法、hashCode()方法的区别 13、...
    Miley_MOJIE阅读 3,744评论 0 11
  • 1、眼动、脑电实验2、可用性测试用户在一定场景下使用产品,发现用户在使用过程中的偏好、需求、痛点、路径、习惯等,为...
    jlnbda3488375阅读 324评论 0 0