Given an array that is initially stored in one stack, sort it with one additional stacks (total 2 stacks).

After sorting the original stack should contain the sorted integers and from top to bottom the integers are sorted in ascending order.

Assumptions:

• The given stack is not null.

Requirements:

• No additional memory, time complexity = O(n ^ 2).

 

基于selection sort，一个stack即当buffer又当output，每次倒的时候记录global min及出现次数（以防重复元素）

time: O(n^2), space: O(n)

public class Solution {  public void sort(LinkedList
     
       s1) {    LinkedList
      
        s2 = new LinkedList
       
        ();    // Write your solution here.    if(s1 == null || s1.size() < 0) {      return;    }    int cnt = 0;    while(!s1.isEmpty()) {      int globalMin = Integer.MAX_VALUE;      while(!s1.isEmpty()) {        int tmp = s1.pop();        if(tmp < globalMin) {          globalMin = tmp;        }        s2.push(tmp);      }      while(!s2.isEmpty() && s2.peek() >= globalMin) {        int tmp = s2.pop();        if(tmp == globalMin) {          cnt++;        } else {          s1.push(tmp);        }      }      while(cnt > 0) {        s2.push(globalMin);        cnt--;      }    }        while(!s2.isEmpty()) {      s1.push(s2.pop());    }  }}