0414._third_maximum_number.md

414. Third Maximum Number

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/third-maximum-number/description/

内容描述

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

先对nums去重

因为下面的例子

Input: [2, 2, 3, 1]

Output: 1

如果更新后的nums长度小于3，说明不存在第三大的数字，直接返回最大值即可

用一个size为3的最小堆装下更新后的nums的前3个数字，循环遍历，遇到比堆顶大的数字就pop堆顶元素，push当前num， 最后堆里面最小的数字就是第三大的数字

beats 43.86%

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = list(set(nums))
        
        if len(nums) < 3:
            return max(nums)
        
        top3 = sorted(nums[:3])
        
        for num in nums[3:]:
            if num > top3[0]:
                heapq.heappop(top3)
                heapq.heappush(top3, num)
                
        return top3[0]

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

用三个变量来记录，max， secondmax, thirdmax，

• 遇到比max还大的就更新，当前max降级为second max，当前secondmax降级为third max
• 遇到比max小但是比second max大的也这样做降级处理
• 更新third max

类似的题目有第314题

beats 100%

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = list(set(nums))
        
        if len(nums) < 3:
            return max(nums)
        
        first = second = third = -sys.maxsize
        for num in nums:
            if num > first:
                third = second
                second = first
                first = num
            elif num < first and num > second:
                third = second
                second = num
            elif num < second and num > third:
                third = num
        return third