Skip to content

Commit 823d42e

Browse files
halfrosthalfrost
committed
Fix solution 628
1 parent bfb9839 commit 823d42e

File tree

2 files changed

+47
-40
lines changed

2 files changed

+47
-40
lines changed

‎leetcode/0628.Maximum-Product-of-Three-Numbers/628. Maximum Product of Three Numbers.go

Lines changed: 20 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
package leetcode
22

33
import (
4+
"math"
45
"sort"
56
)
67

@@ -32,28 +33,27 @@ func max(a int, b int) int {
3233

3334
// 解法二 模拟，时间复杂度 O(n)
3435
func maximumProduct1(nums []int) int {
35-
n1, n2, n3 := -1<<63, -1<<63, -1<<63
36-
n4, n5 := 0, 0
37-
for _, v := range nums {
38-
if v > n1 {
39-
n3 = n2
40-
n2 = n1
41-
n1 = v
42-
} else if v > n2 {
43-
n3 = n2
44-
n2 = v
45-
} else if v > n3 {
46-
n3 = v
36+
max := make([]int, 0)
37+
max = append(max, math.MinInt64, math.MinInt64, math.MinInt64)
38+
min := make([]int, 0)
39+
min = append(min, math.MaxInt64, math.MaxInt64)
40+
for _, num := range nums {
41+
if num > max[0] {
42+
max[0], max[1], max[2] = num, max[0], max[1]
43+
} else if num > max[1] {
44+
max[1], max[2] = num, max[1]
45+
} else if num > max[2] {
46+
max[2] = num
4747
}
48-
if v < n4 {
49-
n5 = n4
50-
n4 = v
51-
} else if v < n5 {
52-
n5 = v
48+
if num < min[0] {
49+
min[0], min[1] = num, min[0]
50+
} else if num < min[1] {
51+
min[1] = num
5352
}
5453
}
55-
if n2*n3 > n4*n5 {
56-
return n1 * n2 * n3
54+
maxProduct1, maxProduct2 := min[0]*min[1]*max[0], max[0]*max[1]*max[2]
55+
if maxProduct1 > maxProduct2 {
56+
return maxProduct1
5757
}
58-
return n1 * n4 * n5
58+
return maxProduct2
5959
}

‎website/content/ChapterFour/0628.Maximum-Product-of-Three-Numbers.md

Lines changed: 27 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ Given an integer array, find three numbers whose product is maximum and output t
4343
package leetcode
4444

4545
import (
46+
"math"
4647
"sort"
4748
)
4849

@@ -65,32 +66,38 @@ func maximumProduct(nums []int) int {
6566
return max(nums[0]*nums[1]*nums[len(nums)-1], nums[len(nums)-1]*nums[len(nums)-2]*nums[len(nums)-3])
6667
}
6768

69+
func max(a int, b int) int {
70+
if a > b {
71+
return a
72+
}
73+
return b
74+
}
75+
6876
// 解法二 模拟，时间复杂度 O(n)
6977
func maximumProduct1(nums []int) int {
70-
n1, n2, n3 := -1<<63, -1<<63, -1<<63
71-
n4, n5 := 0, 0
72-
for _, v := range nums {
73-
if v > n1 {
74-
n3 = n2
75-
n2 = n1
76-
n1 = v
77-
} else if v > n2 {
78-
n3 = n2
79-
n2 = v
80-
} else if v > n3 {
81-
n3 = v
78+
max := make([]int, 0)
79+
max = append(max, math.MinInt64, math.MinInt64, math.MinInt64)
80+
min := make([]int, 0)
81+
min = append(min, math.MaxInt64, math.MaxInt64)
82+
for _, num := range nums {
83+
if num > max[0] {
84+
max[0], max[1], max[2] = num, max[0], max[1]
85+
} else if num > max[1] {
86+
max[1], max[2] = num, max[1]
87+
} else if num > max[2] {
88+
max[2] = num
8289
}
83-
if v < n4 {
84-
n5 = n4
85-
n4 = v
86-
} else if v < n5 {
87-
n5 = v
90+
if num < min[0] {
91+
min[0], min[1] = num, min[0]
92+
} else if num < min[1] {
93+
min[1] = num
8894
}
8995
}
90-
if n2*n3 > n4*n5 {
91-
return n1 * n2 * n3
96+
maxProduct1, maxProduct2 := min[0]*min[1]*max[0], max[0]*max[1]*max[2]
97+
if maxProduct1 > maxProduct2 {
98+
return maxProduct1
9299
}
93-
return n1 * n4 * n5
100+
return maxProduct2
94101
}
95102

96103
```

0 commit comments

Comments
 (0)