Question: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
Question Name: Best Time to Buy and Sell Stock IV
Thanks to genius solution from @yishiluo.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | import heapq class TopN: def __init__(self, n): assert(n > 0) self.maximum = n self.content = [] def add(self, value): if len(self.content) < self.maximum: heapq.heappush(self.content, value) elif self.content[0] < value: heapq.heappushpop(self.content, value) def result(self): return self.content def debug_info(self): print "Content(max:", self.maximum,"):", self.content class Solution: # @param {integer} k # @param {integer[]} prices # @return {integer} def maxProfit(self, k, prices): if len(prices) < 2 or k < 1: return 0 stack = [] profitable = TopN(k) valley = 0 peak = -1 while valley < len(prices): # Find the next profitable transaction. while valley < len(prices) - 1 and prices[valley] >= prices[valley + 1]: valley += 1 if valley == len(prices) - 1: break peak = valley + 1 while peak < len(prices) -1 and prices[peak] < prices[peak + 1]: peak += 1 # Try to finalize or combine with previous transactions. valley_price = prices[valley] peak_price = prices[peak] while len(stack) != 0 and stack[-1][0] >= valley_price: transaction = stack.pop() profitable.add(transaction[1] - transaction[0]) while len(stack) != 0 and stack[-1][1] <= peak_price: transaction = stack.pop() profitable.add(transaction[1] - valley_price) valley_price = transaction[0] # Finish processing current transaction. stack.append([valley_price, peak_price]) valley = peak + 1 # Finalize all the remaining transactions. for transaction in stack: profitable.add(transaction[1] - transaction[0]) return sum(profitable.result()) |