双栈排序 牛客网 程序员面试金典 C++ Python
题目描述
请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
给定一个int[] numbers(C++中为vector<int>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到最后一个元素。
测试样例：
[1,2,3,4,5]
返回：[5,4,3,2,1]
C++
class TwoStacks { public: //run:7ms memory:480k vector<int> twoStacksSort(vector<int> numbers) { int n = numbers.size(); if(n<=1)return numbers; stack<int> st1; stack<int> st2; int temp; for(int i=0;i<n;i++){ temp = numbers[i]; while(!st1.empty() && temp < st1.top()){ st2.push(st1.top()); st1.pop(); } st1.push(temp); while(!st2.empty()){ st1.push(st2.top()); st2.pop(); } } vector<int> v; while(!st1.empty()){ v.push_back(st1.top()); st1.pop(); } return v; } };Python
class TwoStacks: #run:116ms memory:5728k def twoStacksSort(self, numbers): if None == numbers: return None if 1 == len(numbers): return numbers tmp = None s1 = [] s2 = [] for i in range(len(numbers)): tmp = numbers[i] while s1 and tmp < s1[- 1]: s2.append(s1[- 1]) s1.pop() s1.append(tmp) while s2: s1.append(s2[ - 1]); s2.pop() while s1: s2.append(s1[-1]) s1.pop() return s2
转载于:https://www.cnblogs.com/vercont/p/10210330.html
