Fastest ever Python O(N)


  • 0

    The idea is from @yishiluo. I just made minor improvement on unneccessary operations and used quick select to get top K elements.
    The idea is that we convert this problem to find maximum K subarray, finding K non-overlap intervals that have the max sum.

    import heapq, random
    class Solution(object):
        def findKthLargest(self, nums, k):
            def quickselect(start, end, nums, k):
                if start == end:
                    return nums[start]
                    
                mid = partition(start, end, nums)
                
                if mid == k:
                    return nums[mid]
                elif k > mid:
                    return quickselect(mid + 1, end, nums, k)
                else:
                    return quickselect(start, mid - 1, nums, k)
            
            def partition(start, end, nums):
                p = random.randrange(start, end + 1)
                pv = nums[p]
                nums[end], nums[p] = nums[p], nums[end]
                mid = start
                for i in xrange(start, end):
                    if nums[i] >= pv:
                        nums[i], nums[mid] = nums[mid], nums[i]
                        mid += 1
                nums[mid], nums[end] = nums[end], nums[mid]
                return mid
            
            return quickselect(0, len(nums) - 1, nums, k - 1)
        
        def maxProfit(self, k, prices):
            if not prices:
                return 0
            stack = []
            heap = []
            v = p = 0
            n = len(prices)
            ans = 0
            while p < n:
                v = p
                while v < n - 1 and prices[v] >= prices[v + 1]:
                    v += 1
                p = v + 1
                while p < n and prices[p] > prices[p - 1]:
                    p += 1
                while stack and prices[stack[-1][0]] > prices[v]:
                    _v, _p = stack.pop()
                    heap.append(prices[_p - 1] - prices[_v])
                while stack and prices[stack[-1][1] - 1] < prices[p - 1]:
                    heap.append(prices[stack[-1][1] - 1] - prices[v])
                    v, _ = stack.pop()
                stack.append((v, p))
            
            heap += [prices[p - 1] - prices[v] for v, p in stack]
            if len(heap) < k:
                return sum(heap)
            self.findKthLargest(heap, k)
            return sum(heap[:k])
    
    # 48ms, beats 100%
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.