Listalla on kokonaisluvut [1,2,3,...,n] jossakin järjestyksessä. Tehtäväsi on selvittää, onko lista mahdollista järjestää pinon avulla.

Järjestämisessä käyt läpi listan alkiot vasemmalta oikealle. Jokaisen alkion kohdalla siirrät ensin alkion joko pinoon tai tuloslistan loppuun, minkä jälkeen voit siirtää pinosta haluamasi määrän alkioita tuloslistan loppuun. Tavoitteena on, että lopuksi kaikki alkiot ovat tuloslistalla järjestyksessä.

Voit olettaa, että listalla on enintään 10^5 alkiota. Tavoitteena on, että algoritmin aikavaativuus on O(n).

Python

Toteuta tiedostoon stacksort.py funktio check, joka ilmoittaa, voiko listan järjestää pinon avulla.

def check(t):
    # TODO

if __name__ == "__main__":
    print(check([1,2,3,4])) # True
    print(check([4,3,2,1])) # True
    print(check([3,4,1,2])) # False
    print(check([1])) # True
    print(check([5,4,3,1,2,6])) # True

Java

Toteuta tiedostoon StackSort.java metodi check, joka ilmoittaa, voiko listan järjestää pinon avulla.

public class StackSort {
    public boolean check(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        StackSort s = new StackSort();
        System.out.println(s.check(new int[] {1,2,3,4})); // true
        System.out.println(s.check(new int[] {4,3,2,1})); // true
        System.out.println(s.check(new int[] {3,4,1,2})); // false
        System.out.println(s.check(new int[] {1})); // true
        System.out.println(s.check(new int[] {5,4,3,1,2,6})); // true
    }
}