给定一个int[] numbers(C++中为vector<int>),其中第一个元素为栈顶,请编写程序将栈进行升序排列(即最大元素位于栈顶),返回排序后的栈。要求最多使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。并注意这是一个栈,意味着排序过程中只能访问到最后一个元素。
测试样例:
[1,2,3,4,5]
返回:[5,4,3,2,1]
思路:
1. 先看下图
初始栈initStack中存放的数组中待排序的数;临时栈tempStack中存放的是已经排好序的数。
现在继续对初始栈中的数进行排序,5应当插入到临时栈哪个位置?
2. 5应该插入到8下,3上。
具体如何操作呢?
首先初始栈initStack弹出待排序的数5,存入变量tmp;而临时栈tempStack弹出比5大的数,并存入初始化栈initStack中。如下图:
3. 将变量tmp保存的数插入到临时栈tempStack中去,由于初始化栈initStack中8,12是排好序的,可以再直接弹入临时栈中,再对下一个数10进行如上操作。
代码如下:
import java.util.*;
public class TwoStacks {
public ArrayList<Integer> twoStacksSort(int[] numbers) {
ArrayList<Integer> list = new ArrayList<Integer>();
//构建栈,并初始化栈
Stack<Integer> initStack = new Stack<>();
for (int i = 0 ; i < numbers.length; i++){
initStack.push(numbers[i]);
}
//构建辅助栈,用来存放排好序的数
Stack<Integer> tempStack = new Stack<>();
while(!initStack.isEmpty()){
if (tempStack.isEmpty()){
tempStack.push(initStack.pop());
}else {
//新建变量,存储原始栈中待排序的栈
int tmp = initStack.pop();
//将辅助栈中的排好序中的大于tmp的数放入原始栈中
while (!tempStack.isEmpty() && tempStack.peek() > tmp){
initStack.push(tempStack.pop());
}
//辅助栈存储之前保存的变量
tempStack.push(tmp);
}
}
while(!tempStack.isEmpty()){
list.add(tempStack.pop());
}
return list;
}
}
public class TwoStacks { public ArrayList<Integer> twoStacksSort(int[] numbers) { // write code here ArrayList<Integer> result = new ArrayList<>(numbers.length); //初始化原始栈 Stack<Integer> stack = new Stack<>(); int index = numbers.length - 1; for (int i = index; i >= 0; i--) { stack.push(numbers[i]); } Stack<Integer> resultStack = new Stack<>();//额外的栈 while (!stack.empty()) { if (resultStack.empty()) { resultStack.push(stack.pop()); } else { int a = stack.pop(); int b = resultStack.pop(); if (a < b) { stack.push(b); while (!resultStack.empty() && a < (b = resultStack.pop())) { stack.push(b); } } if (a >= b) { resultStack.push(b); } resultStack.push(a); } } //返回ArrayList结果 while (!resultStack.empty()) { result.add(resultStack.pop()); } return result; }
public ArrayList<Integer> twoStacksSort(int[] numbers) { /* * 思路: * 只用两个栈排序,一个是有序的asc,另一个是无序的buffer就可以实现对一个栈的排序。如何有序,当原始栈只有一个时就有序了 * numbers中第一个为栈顶 * 主要是解决buffer栈顶元素放在asc的位置 * 1. buffer栈顶大于等于asc栈顶或asc空 * 直接放 * 2. buffer栈顶小于asc栈顶 * buffer栈顶值出栈,临时变量存放buffer栈顶值 * 循环从asc中拿出值放到buffer直至asc空或满足1条件 */ if(numbers == null || numbers.length == 0){ return null; } int length = numbers.length; ArrayList<Integer> res = new ArrayList<Integer>(length); Stack<Integer> buffer = new Stack<Integer>(); Stack<Integer> ascStack = new Stack<Integer>(); //初始状态,buffer中放了length-1个与numbers逆序的数串,asc只剩栈底元素 for(int i = 0; i < length-1; i++){ buffer.push(numbers[i]); } ascStack.push(numbers[length-1]); //排序 int bufTop = 0; while(buffer.size() > 0){ if(ascStack.isEmpty() || buffer.peek() >= ascStack.peek()){ ascStack.push(buffer.pop()); }else{ bufTop = buffer.pop(); int count_curBuffer = buffer.size(); while(!ascStack.isEmpty() && bufTop < ascStack.peek()){ buffer.push(ascStack.pop()); } ascStack.push(bufTop); int count_numsFromAsc = buffer.size()-count_curBuffer; for(int i = 0; i < count_numsFromAsc; i++){ ascStack.push(buffer.pop()); } } } for(int i = 0; i < length; i++){ res.add(ascStack.pop()); } return res; }
class TwoStacks { public: vector<int> twoStacksSort(vector<int> numbers) { // write code here vector<int> forSort; if(numbers.size() <= 1) return numbers; forSort.push_back(numbers.back()); numbers.pop_back(); while(numbers.size() > 0) { int temp = numbers.back(); numbers.pop_back(); int popNum = 0; // 出栈元素的数量 while(!forSort.empty() && temp < forSort.back()){ numbers.push_back(forSort.back()); forSort.pop_back(); popNum++; } forSort.push_back(temp); while(popNum > 0){ forSort.push_back(numbers.back()); numbers.pop_back(); popNum--; } } reverse(forSort.begin(),forSort.end()); return forSort; } };插入排,一个作为备用存储临时元素。
vector<int> twoStacksSort(vector<int> numbers) { vector<int> stack; while(!numbers.empty()){ int num = numbers.back(); numbers.pop_back(); while(!stack.empty() && num > stack.back()){ numbers.push_back(stack.back()); stack.pop_back(); } stack.push_back(num); } return stack; }
import java.util.*; /* 是左程云《程序员代码指南》里的 要排序的栈为stack,辅助的栈为help,在stack上执行pop操作,弹出的元素记为cur 1.如果cur小于或者等于help的栈顶元素,则将cur直接压入help(目的是要小的放在下面) 2.如果cur大于help的栈顶元素,则将help的元素逐一弹出,逐一压入stack,直到1 就是为了将小的数都放在help的底下 */ public class TwoStacks { public ArrayList<Integer> twoStacksSort(int[] numbers) { // write code here Stack<Integer> stack=new Stack<Integer>(); Stack<Integer> help=new Stack<Integer>(); ArrayList<Integer> list=new ArrayList<Integer>(); for(int i=0;i<numbers.length;i++) stack.push(numbers[i]); while(!stack.isEmpty()){ int cur =stack.pop(); while(!help.isEmpty()&& help.peek()>cur ){ //比cur大 出栈 stack.push(help.pop()); } help.push(cur); } while(!help.isEmpty()){ list.add(stack.push(help.pop())); } return list; } }
class TwoStacks { public: vector<int> twoStacksSort(vector<int> numbers) { // write code here stack<int> a; stack<int> b; int siz = numbers.size(); for(int i = 0; i < siz; i++){ a.push(numbers[i]); } for(int i = 0; i < siz; i++){ int min = a.top(); int count = 0; for(int j = i; j < siz; j++){ if(a.top() < min){ min = a.top(); } b.push(a.top()); a.pop(); } a.push(min); for(int j = i; j < siz; j++){ if(count == 0 && b.top() == min){ b.pop(); count++; continue; } a.push(b.top()); b.pop(); } } for(int i = 0; i < siz; i++){ numbers[i] = a.top(); a.pop(); } return numbers; } };
class TwoStacks { public: vector<int> twoStacksSort(vector<int> numbers) { vector<int> help; while (!numbers.empty()) { int cur = numbers.back(); numbers.pop_back(); while (!help.empty() && cur < help.back()) { numbers.push_back(help.back()); help.pop_back(); } help.push_back(cur); } numbers.clear(); while (!help.empty()) { numbers.push_back(help.back()); help.pop_back(); } return numbers; } };
好想知道为什么不用stack<int>而要用vector<int>? vector<int>的第一个元素是栈顶的话,操作起来好麻烦啊。 这里我投机取巧了,把vector的最后的一个元素当做栈顶,每次移动栈顶的操作就是 pop_back(),每次获取栈顶元素就直接用back()。 思路很简单啊,就两点: 1. 如果栈顶元素cur<=辅助栈help栈顶元素,那么就直接push入辅助栈。 2. 否则,就将辅助栈的栈顶元素push到原栈,直至cur>辅助栈的栈顶元素,此时再将cur push入辅助栈。保证辅助栈的数据是从栈顶到栈底升序,最后将辅助栈的数据逆序push到原栈 就可以使得原栈是降序啦~
public ArrayList<Integer> twoStacksSort(int[] numbers) { if(numbers==null || numbers.length<1) return null; Stack<Integer> myStack1 = new Stack<Integer>(); Stack<Integer> myStack2 = new Stack<Integer>(); ArrayList<Integer> myResult = new ArrayList<Integer>(); for(int i=0;i<numbers.length;i++){ myStack1.push(numbers[i]); } while(!myStack1.empty()){ int myTemp=myStack1.pop(); while(!myStack2.empty() && myStack2.peek()>myTemp){ myStack1.push(myStack2.pop()); } myStack2.push(myTemp); } while(!myStack2.empty()){ myResult.add(myStack2.pop()); } return myResult; }
//看到题目蛋碎一地,说好的是栈,你给我一个数组是什么意思,人与人之间最基本的信任呢 //还只让我用一个额外栈,结果输出是个ArrayList,如果照题目意思把ArrayList也当成一个栈。。。那还要啥自行车 //我的内心是崩溃的,然后就有了这样的写法 //思路,取出栈1中元素放在栈2中,然后栈1再弹出一个元素,比较这个元素与栈2顶元素大小,如果大于等于栈二顶元素,就把它压入栈2中,如果小于,就把栈2中元素弹出一个压入栈1中,重复比较,直到元素大于栈2顶元素或栈2为空,就把它压入栈2中,实现排序。 //方法一: public ArrayList<Integer> twoStacksSort(int[] numbers) { ArrayList<Integer> result=new ArrayList<Integer>(); if(numbers==null) return result; int count=0,temp=0,index=0; while(index<numbers.length){ temp=count==0?numbers[index++]:temp; if(result.size()==0||temp>=result.get(0)){ result.add(0,temp); // while(count-->0) result.add(0,numbers[index++]);//这句话可以不要 count=0; } else { numbers[--index]=result.remove(0); count++; } } return result; } //方法二,原理同方法一,不让我用栈我偏用,我是菜鸟我怕谁QAQ public ArrayList<Integer> twoStacksSort(int[] numbers) { ArrayList<Integer> result=new ArrayList<Integer>(); if(numbers==null) return result; Stack<Integer> stack= new Stack<Integer>(); Stack<Integer> resultStack= new Stack<Integer>(); for(int i=0;i<numbers.length;i++) stack.push(numbers[numbers.length-i-1]); int count=0,temp=0; while(!stack.isEmpty()){ temp=count==0?stack.pop():temp; if(resultStack.isEmpty()||temp>=resultStack.peek()){ resultStack.push(temp); // while(count-->0) resultStack.push(stack.pop());//这句话可以不要,不过不知道为什么加上这句话,运行占用内存是1000多K,不加是3000多K count=0; } else { stack.push(resultStack.pop()); count++; } } while(!resultStack.isEmpty()) result.add(resultStack.pop()); return result; }
//解题思路:一个原栈,一个辅助栈,我们可以将原栈中的元素依次出栈和辅助栈中的栈顶元素进行比较,如果原大于辅,将原出栈到辅助中,
class TwoStacks { public: vector<int> twoStacksSort(vector<int> numbers) { // write code here vector<int> temp; temp.push_back(numbers.back()); numbers.pop_back(); while(!numbers.empty()){ int n=numbers.back(); numbers.pop_back(); while(!temp.empty()&&n>temp.back()){//下沉操作,弹出到temp中不小于n的位置 numbers.push_back(temp.back());//temp弹出的数放到numbers中 temp.pop_back(); } temp.push_back(n); } return temp; } };
public ArrayList<Integer> twoStacksSort(int[] numbers) { // write code here ArrayList<Integer> stack=new ArrayList<Integer>(); int temp,i; for(i=0;i<numbers.length;i++){ temp=numbers[i]; while(!stack.isEmpty()&&stack.get(stack.size()-1)<temp){ numbers[i--]=stack.get(stack.size()-1); stack.remove(stack.size()-1); } stack.add(temp); } return stack; }
class TwoStacks: def twoStacksSort(self, numbers): #return sorted(numbers,reverse=True) if not numbers&nbs***bsp;len(numbers)==1: return numbers res = [] while numbers: if not res: res.append(numbers.pop()) else: pre = numbers.pop() if pre<=res[-1]: res.append(pre) else: while res and res[-1]<pre: numbers.append(res.pop()) res.append(pre) return res
class TwoStacks { public: vector<int> twoStacksSort(vector<int> numbers) { vector<int> temp_stack; int temp; while(!numbers.empty()){ temp = numbers.back(); numbers.pop_back(); while(!temp_stack.empty() && temp_stack.back() < temp) { numbers.push_back(temp_stack.back()); temp_stack.pop_back(); } temp_stack.push_back(temp); } return temp_stack; } };
class TwoStacks { public: vector<int> twoStacksSort(vector<int> numbers) { vector<int> res; while (!numbers.empty()) { int num = numbers.back(); numbers.pop_back(); while (!res.empty() && res.back() < num) { numbers.push_back(res.back()); res.pop_back(); } res.push_back(num); } return res; } };
运行时间:6ms
占用内存:504k
时间复杂度O(N^2),空间复杂度O(N)classTwoStacks {public:vector<int> twoStacksSort(vector<int> numbers) {// write code herevector<int> buf;while(!numbers.empty()){int top = numbers[0];numbers.erase(numbers.begin());while(!buf.empty()&&(top<buf[0])){numbers.insert(numbers.begin(),buf[0]);buf.erase(buf.begin());}buf.insert(buf.begin(),top);}return buf;}};
//构建一个辅助栈存放排好序的 和 一个变量存放临时值
public ArrayList<Integer> twoStacksSort(int[] numbers) {
ArrayList<Integer> res = new ArrayList<>();
if (numbers == null || numbers.length == 0) return res;
Stack<Integer> stack1 = new Stack<>();//原始栈
for (int i = numbers.length - 1; i >= 0; i--)
stack1.push(numbers[i]);
int temp;//存放临时值
Stack<Integer> stack2 = new Stack<>();
while (stack1.size() != 0) {
temp = stack1.pop();
while (stack2.size() != 0 && stack2.peek() > temp) {//辅助栈不为空,且栈头元素比临时值大
stack1.push(stack2.pop());
}
stack2.push(temp);
}
while (stack2.size() != 0) {
res.add(stack2.pop());
}
return res;
}