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

今天开始，试着用Python实现《真实世界的算法》中的算法

股票跨度

一只股票的价格在某天的跨度（span）是指这一天之前连续多少天股票价格低于或等于这天的价格。

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]