《真實世界的算法》（一）

今天開始，試著用Python實現《真實世界的算法》中的算法

股票跨度

一只股票的價格在某天的跨度（span）是指這一天之前連續(xù)多少天股票價格低于或等于這天的價格。

quotes = [7,11,8,6,3,8,9]
spans = []
for i in range(7):
    k = 1
    span_end = False
    while i-k >= 0 and not span_end:
        if quotes[i-k] <= quotes[i]:
            k += 1
        else:
            span_end = True
    spans.append(k)
print(spans)

[1, 2, 1, 1, 1, 4, 5]

使用棧的股票跨度算法

class Stack(object):

    def __init__(self):
        self.stack = []

    def isEmpty(self):
        """
        棧是否為空
        """
        return self.stack == []

    def push(self, data):
        """
        進棧函數
        """
        self.stack.append(data)

    def pop(self):
        """
        出棧函數，
        """
        return self.stack.pop()

    def gettop(self):
        """
        取棧頂
        """
        return self.stack[-1]

def StackStockSpan():
    quotes = [7,11,8,6,3,8,9]
    spans = []
    stack = Stack()
    stack.push(0)
    for i in range(7):
        while not stack.isEmpty() and quotes[stack.gettop()] <= quotes[i]:
            stack.pop()
        if stack.isEmpty():
            spans.append(i+1)
        else:
            spans.append(i-stack.gettop())
        stack.push(i)
    return spans

if __name__ == "__main__":
    print(StackStockSpan())

[1, 2, 1, 1, 1, 4, 5]