O(n) Python Solution


  • -1
    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if nums == []:
                return 0
            length = len(nums)
            queue = []
            anwer = 1
            for i in xrange(length):
                while queue and queue[-1] >= nums[i]:
                    queue.pop()
                if queue == [] or queue[-1] < nums[i]:
                    queue.append(nums[i])
                    anwer = max(anwer, len(queue))
            queue = []
            for i in xrange(length-1, -1, -1):
                while queue and queue[-1] <= nums[i]:
                    queue.pop()
                if queue == [] or queue[-1] > nums[i]:
                    queue.append(nums[i])
                    anwer = max(anwer, len(queue))
            return anwer
    

    UPDATE:

    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            length = len(nums)
            dpl, dpr = [0] * length, [0] * length
            stack = []
            for i in xrange(length):
                while stack and nums[stack[-1]] >= nums[i]:
                    stack.pop()
                stack.append(i)
                dpl[i] = len(stack) 
            stack = []
            for i in xrange(length-1,-1, -1):
                while stack and nums[stack[-1]] <= nums[i]:
                    stack.pop()
                stack.append(i)
                dpr[i] = len(stack)
            answer = 0
            for i in xrange(length):
                answer = max(answer, dpl[i]+dpr[i]-1)
            return answer
    

    UPDATE:

    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            stack = []
            length = len(nums)
            answer = [0] * length
            unsovle = []
            l = 0
            for i in xrange(length):
                if stack and nums[stack[-1]] == nums[i]:
                    answer[i] = answer[stack[-1]]
                    continue
                if not unsovle:
                    if not stack or nums[i] > nums[stack[-1]]:
                        stack.append(i)
                        answer[i] = answer[i-1]+1
                        l = max(answer[i], l)
                    else:
                        e = stack[-1]
                        while stack and nums[stack[-1]] >= nums[i]:
                            stack.pop()
                        if not stack:
                            unsovle.append((0, e))
                            answer[i] = 1
                        else:
                            unsovle.append((stack[-1], e))
                            answer[i] = answer[stack[-1]]+1
                        while stack:
                            stack.pop()
                        stack.append(i)
                else:
                    if nums[i] <= nums[unsovle[-1][1]]:
                        if not stack or nums[i] > nums[stack[-1]]:
                            stack.append(i)
                            answer[i] = answer[i-1]+1
                            l = max(answer[i], l)
                        else:
                            e = stack[-1]
                            while stack and nums[stack[-1]] >= nums[i]:
                                stack.pop()
                            if not stack:
                                unsovle.append((0, e))
                                answer[i] = 1
                            else:
                                unsovle.append((stack[-1], e))
                                answer[i] = answer[stack[-1]]+1
                            while stack:
                                stack.pop()
                            stack.append(i)
                    else:
                        while unsovle and nums[unsovle[-1][1]] < nums[i]:
                            t = unsovle.pop()
                            tmp = answer[t[1]] - answer[t[0]]
                            answer[i] = max(answer[i], answer[t[0]] + max(tmp+1, len(stack)+1))
                            l = max(answer[i], l)
                        stack.append(i)
            return l
    

    Special thanks to @ccyyatnet


  • 0
    B

    can you give some explaination?


  • 0
    A

    How come it's a O(n) solution?


  • 0
    C

    wrong for [2,3,7,4,5,1,6]
    your answer: 4
    right answer: 5


  • 0
    This post is deleted!

  • 0

    right @ccyyatnet, thanks for letting me know that mistake, I have updated my code now :)


  • 0

    Please check the updated code :)


  • 0

    That one does not make sense, try to check the new one


  • 0
    C

    sorry..the new one still wrong on [2,3,1,4,5,8,6,7]


  • 0

    Thanks for pointing out this issue, I have updated my code now :)


  • 0
    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            stack = []
            length = len(nums)
            answer = [0] * length
            unsovle = []
            l = 0
            for i in xrange(length):
                if stack and nums[stack[-1]] == nums[i]:
                    answer[i] = answer[stack[-1]]
                    continue
                if not unsovle:
                    if not stack or nums[i] > nums[stack[-1]]:
                        stack.append(i)
                        answer[i] = answer[i-1]+1
                        l = max(answer[i], l)
                    else:
                        e = stack[-1]
                        while stack and nums[stack[-1]] >= nums[i]:
                            stack.pop()
                        if not stack:
                            unsovle.append((0, e))
                            answer[i] = 1
                        else:
                            unsovle.append((stack[-1], e))
                            answer[i] = answer[stack[-1]]+1
                        while stack:
                            stack.pop()
                        stack.append(i)
                else:
                    if nums[i] <= nums[unsovle[-1][1]]:
                        if not stack or nums[i] > nums[stack[-1]]:
                            stack.append(i)
                            answer[i] = answer[i-1]+1
                            l = max(answer[i], l)
                        else:
                            e = stack[-1]
                            while stack and nums[stack[-1]] >= nums[i]:
                                stack.pop()
                            if not stack:
                                unsovle.append((0, e))
                                answer[i] = 1
                            else:
                                unsovle.append((stack[-1], e))
                                answer[i] = answer[stack[-1]]+1
                            while stack:
                                stack.pop()
                            stack.append(i)
                    else:
                        while unsovle and nums[unsovle[-1][1]] < nums[i]:
                            t = unsovle.pop()
                            tmp = answer[t[1]] - answer[t[0]]
                            answer[i] = max(answer[i], answer[t[0]] + max(tmp+1, len(stack)+1))
                            l = max(answer[i], l)
                        stack.append(i)
            return l

Log in to reply
 

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