得物0509面试手撕题目解答

题目

使用两个栈（一个无序栈和一个空栈）将无序栈中的元素转移到空栈，使其有序，不允许使用其他数据结构。

示例：输入：[3, 1, 6, 4, 2, 5]，输出：[6, 5, 4, 3, 2, 1]

思路与代码

如果不限制使用其他数据结构，大可以直接全部输出到数组里面然后快速排序(bushi)

但是这道题目不允许使用其他数据结构，那么只能用原来的无序栈保存不能压入有序栈的元素。

• 从stack1弹出元素temp，并将stack2中所有比temp小的元素移回stack1。

• 将temp压入stack2，确保stack2始终降序。

• 此时，被移回stack1中的元素一定小于temp，不满足判断条件，所以将依次执行temp = stack1.pop()和stack2.append(temp)

读者可以模拟插入排序的过程来理解本题，下面的代码展示的是降序排列的过程：

def sort_stack(stack1):stack2 = []# 将stack1中的元素按降序插入stack2（从栈底到栈顶）while stack1:temp = stack1.pop()# 将stack2中比temp小的元素移回stack1while stack2 and stack2[-1] < temp:  # 当栈2不为空且栈2的栈顶元素小于tempstack1.append(stack2.pop())stack2.append(temp)print(stack2)return stack2sort_stack([3, 1, 6, 4, 2, 5])
# [6, 5, 4, 3, 2, 1]

若要改为升序排列，只需将判断条件改为stack2[-1] > temp：

def sort_stack(stack1):stack2 = []# 将stack1中的元素按升序插入stack2（从栈底到栈顶）while stack1:temp = stack1.pop()# 将stack2中比temp大的元素移回stack1while stack2 and stack2[-1] > temp:  # 当栈2不为空且栈2的栈顶元素大于tempstack1.append(stack2.pop())stack2.append(temp)print(stack2)return stack2sort_stack([3, 1, 6, 4, 2, 5])
# [1, 2, 3, 4, 5, 6]