Maksimilista

Tehtäväsi on toteuttaa luokka, joka pitää yllä listaa luvuista sekä tarjoaa metodin, jonka avulla voidaan hakea tehokkaasti listan suurin luku.

Toteuta tiedostoon maxlist.py luokka MaxList, jossa on seuraavat metodit:

• append(number): lisää luku listan loppuun
• max(): ilmoita listan suurin luku

Voit olettaa, että listalla on vähintään yksi luku, kun metodia max kutsutaan. Kummankin metodin tulee toimia tehokkaasti ajassa O(1).

class MaxList:
    def __init__(self):
        # TODO

    def append(self, number):
        # TODO

    def max(self):
        # TODO

if __name__ == "__main__":
    numbers = MaxList()

    numbers.append(1)
    numbers.append(2)
    numbers.append(3)
    print(numbers.max()) # 3

    numbers.append(8)
    numbers.append(5)
    print(numbers.max()) # 8

Tässä listalle lisätään ensin luvut 1, 2 ja 3, minkä jälkeen listan sisältö on [1,2,3] ja suurin luku on 3. Tämän jälkeen lisätään vielä luvut 8 ja 5, minkä jälkeen listan sisältö on [1,2,3,8,5] ja suurin luku on 8.

Voit tutkia ratkaisusi tehokkuutta seuraavan testin avulla. Tässäkin tapauksessa koodin tulisi antaa vastaus välittömästi.

    numbers = MaxList()
    total = 0
    for i in range(10**5):
        numbers.append(i * 999983 % 10**9)
        total += numbers.max()
    print(total) # 99498381797517