《真實(shí)世界的算法》（一）
今天開(kāi)始孽水，試著用Python實(shí)現(xiàn)《真實(shí)世界的算法》中的算法
股票跨度
一只股票的價(jià)格在某天的跨度（span）是指這一天之前連續(xù)多少天股票價(jià)格低于或等于這天的價(jià)格逃呼。
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):
"""
進(jìn)棧函數(shù)
"""
self.stack.append(data)
def pop(self):
"""
出棧函數(shù)揪胃，
"""
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]
