Day 2：414. Third Maximum Number

今日题目

题目：414. Third Maximum Numbe
题目主题：Array, Sorting

我会从最基本的排序开始，本题先不讲任何演算法或资料结构。但我想在今天的这个题目来分享一下，我平常做题目时常使用介面上哪些区块。

简单说说 LeetCode解题介面

做题目的介面如下图：

基本的操作不多做说明，但这边想分享的是我平常做题目时常会使用到的几个区块：

题目说明

这是不看不行的地方，这个区块在讲的是这个题目的目标。
题目范例

题目范例，是会给你几个Testcase让你更了解题目的目标，稍微列几种不同状况出来。这边特别说是因为，这边会列出来的范例不一定是所有状况，只是参考，思考题目时不要被这边的范例绑住，要多思考有没有不同状况的可能性。
题目约束

这个约束的条件，非常重要，像这一题就有提到说不会出现nums里面为空的状态，至少都会有一个数字，往後的题目建议都要习惯先看一下，了解整个题目的限制范围在哪，会对解题很有帮助。
Related Topics

虽然在选题时，大概就会知道了，但通常我还是会再确认一下题目的主题，帮助自己思考解题的方向。
Testcase

这边想特别说的是，Use Example Testcases，点击後会直接帮你把题目范例全部列出来，Run Code时会一次跑所有范例，满方便的。如果想自己多增加几个Testcase，也可以直接换行再增加自己想要的Testcase。
Run Code Result

平常只会显示Your input(输入的Testcases)、Output(现在程序码的输出)、Expected(正确的输出)这三个区块。但如果在程序码中，打上print('xxx')是可以印出来的 (因为是Python所以是使用print) ，会出现一个区块叫stdout，如下图。

如果需要debug时，我自己会用这个方式来确认资料目前的状况。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

本题的目标是在一个nums的所有数字中，过滤掉相同的数字以後，找到第三大的数字。如果最终过滤完相同的数字後剩下数字不到三个，直接回传最大的数字。

约束：

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

范例1

输入：nums = [3,2,1]
输出：1
解释：这是基本范例，数字各一个，直接找到第三大的数字回传即可。

范例2

输入：nums = [1,2]
输出：2
解释：数字不到三个，直接输出最大的数字。

范例3

输入：nums = [2,2,3,1]
输出：1
解释：过滤完重复的数字後会剩3、2、1，因此第三大的数字为1。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

宣告三个变数，分别为第一、第二、第三大的数字。
跑一个回圈，将nums中每个数字跑过一次。
每个数字需检查几种状况：
- 数字已经出现过，直接略过。
- 比第一位置的数字还大，取代第一大的数字。
- 比第二位置的数字还大，取代第二大的数字。
- 比第三位置的数字还大，取代第三大的数字。
- 比第三位置的数字还小的数字，直接略过。
- 检查的位置没值时，直接将数字放在此位置。
若有取代数字的行为发生，要先将当前的值都往後退一个。
若第三大数字没值时，回传第一大位置数字。
若第三大数字有值时，回传第三大数字。

图解过程

范例：nums = [3, 3, 4, 2, 1, 5]

宣告三个变数，分别为第一、第二、第三大的数字。
第一轮 3直接放在第一个位置 / 第二轮 3出现过直接略过。
第三轮 4比3大，将3往後推一个位置，将4放到第一大位置。
第四轮 2小於3跟4，第三位置还没值，直接放在第三位置。
第五轮 1小於第三大的2，直接略过，不处理。
第六轮 5大於目前第一大的4，将目前的值都往後推一个，将5放在第一个位置。
最终因第三大位置有值，输出数字为 3。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        # 宣告三个变数，分别为第一、第二、第三大的数字
        first = nums[0] # 可以直接先把nums中第一个数字给最大的位置
        second = None 
        third = None
        # 因已经先取出第一个数字放在第一大的位置了，因此从nums中第二个数字开始走
        for i in range(1, len(nums)):
            # 过滤相同的数字，出现过数字的不处理
            if nums[i] == first or nums[i] == second or nums[i] == third:
                continue
            # 如果现在数字比第一个大，让第一、第二数字往後退到第二、第三的位置以後
            # 再将数字放在第一大的位置
            if first < nums[i]:
                third = second
                second = first
                first = nums[i]
                continue
            # 如果现在数字比第二个大，第一位置不动
            # 第二位置数字移到第三位置，再将数字放在第二大的位置
            if second == None or second < nums[i]:
                third = second
                second = nums[i]
                continue
            # 如果现在数字比第三个大，第一、第二位置不动
            # 直接将第三数字换成现在的值
            if third == None or third < nums[i]:
                third = nums[i]
                continue
        # 如第三位置有值，直接回传第三大数字
        # 如第三位置没有值，代表过滤完不到三个数字，回传最大数字
        return third if third != None else first