Q002_KIDJourney_solution

[KIDJourney]

Question_ID: Q002

Language: python

Time Cost: 40-mins

Time Complexity: O(nlogn)

Solution

1. build a decrease queue to store max elements.
2. every time new element enter, change the decrease queue.
3. the head of the queue is the max element.

My Code

def lower_bound(l, goal):
    s,e = 0, len(l) - 1
    while s <= e:
        mid = (s+e) // 2
        if l[mid] >= goal:
            s = mid + 1
        else:
            e = mid - 1
    return s

class StackQueue(object):
    def __init__(self):
        self.queue = []
        self.order_queue = []

    def push(self, value):
        self.queue.append(value)
        if self.order_queue:
            if self.order_queue[-1] > value:
                self.order_queue.append(value)
            else:
                pos = lower_bound(self.order_queue, value)
                self.order_queue = self.order_queue[:pos] + [value]
        else:
            self.order_queue = [value]

    def pop(self):
        if not self.queue:
            return -1
        v = self.queue.pop(0)
        if v == self.order_queue[0]:
            self.order_queue.pop(0)
        return v

    def get_max(self):
        if self.order_queue:
            return self.order_queue[0]
        return -1

    def __repr__(self):
        return "{} {}".format(self.queue, self.order_queue)

Other

I think there is a linear solution?