414. Third Maximum Number

Loading...LeetCode

要求时间复杂度O(n)，只能遍历一次。‌

遍历的同时维护top3最大值即可，因为有重复数字，所以用list会很麻烦，直接利用set维护。

class Solution:
    def __init__(self):
        self.max_ = set()
        
    def thirdMax(self, nums: List[int]) -> int:    
        for n in nums:
            self.max_.add(n)
            if len(self.max_)>3:
                self.max_.remove(min(self.max_))
        return min(self.max_) if len(self.max_) == 3 else max(self.max_)