题解 | #CD13 用一个栈实现另一个栈的排序#

两个栈，辅助栈是排好序的，类似于插入排序

• 运行时间：1348ms, 超过78.73% 用Java提交的代码
• 占用内存：23568KB, 超过76.10%用Java提交的代码

两个栈解法微微好于单个栈

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Main mn = new Main();
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int row = Integer.parseInt(sc.readLine());
        String[] ss = sc.readLine().split(" ");
        Deque<Integer> stack = new LinkedList<>();
        Deque<Integer> other = new LinkedList<>();
        for(String s : ss) {
            stack.push(Integer.valueOf(s));
        }
        
        while(!stack.isEmpty()) {
            int cur = stack.pop();
            while(!other.isEmpty() && other.peek() > cur) {
                stack.push(other.pop());
            }
            other.push(cur);
        }
        
        while(!other.isEmpty()){
            System.out.print(other.pop() + " ");
        }
    }
    
//     public static void print(Deque<Integer> stack) {
//         Iterator<Integer> it = stack.iterator();
//         while(it.hasNext()) {
//             System.out.print(it.next() + " ");
            
//         }
//         System.out.println();
//     }
}

单个栈递归解法，类似于冒泡排序

• 运行时间：1657ms, 超过77.16% 用Java提交的代码
• 占用内存：24128KB, 超过75.35%用Java提交的代码

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Main mn = new Main();
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int row = Integer.parseInt(sc.readLine());
        String[] ss = sc.readLine().split(" ");
        Deque<Integer> stack = new LinkedList<>();
        for(String s : ss) {
            stack.push(Integer.valueOf(s));
        }
        for (int i = 0; i < row/2; i++) {
            max(stack, i, 0, stack.peek());
//             Iterator<Integer> it = stack.iterator();
//             while(it.hasNext()) {
//                 System.out.print(it.next() + " ");
                
//             }
//             System.out.println();
        }
        
        while(!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
    
    public static int max(Deque<Integer> stack, int time, int index, int min) {
        if (stack.size() == time) return min;
        
        int cur = stack.pop();
//         System.out.printf("time:%d, index:%d, cur:%d, min:%d\n", time, index, cur, min);
        if (cur < min) {
            int tmp = min;
            min = cur;
            cur = tmp;
        }
        int max = max(stack, time, index+1, min);
//         System.out.printf("time:%d, index:%d, cur:%d, max:%d\n", time, index, cur, max);
        if (max < cur || index == 0) {
            stack.push(max);
            return cur;
        } else {
            stack.push(cur);
            return max;
        }

    }
}