414. Third Maximum Number

Problem

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.

Summary

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

Solution Approach

An easy problem; just dynamically maintain the 3 maximum values. Pay attention to cases where the array contains duplicate data. If there are only 2 numbers or 1 number, just return the maximum among them.

Code


package leetcode

import (
	"math"
)

func thirdMax(nums []int) int {
	a, b, c := math.MinInt64, math.MinInt64, math.MinInt64
	for _, v := range nums {
		if v > a {
			c = b
			b = a
			a = v
		} else if v < a && v > b {
			c = b
			b = v
		} else if v < b && v > c {
			c = v
		}
	}
	if c == math.MinInt64 {
		return a
	}
	return c
}