-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.go
99 lines (87 loc) · 1.95 KB
/
main.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package main
import "fmt"
// 3 2 5 1
// [3] [3,2] [5] [5,1] maxArr
// pop all elements are less than 5
//
// maxArr1(0), maxArr1(1) maxArr1(2)..
// maxArr2(5) maxArr2(4) maxArr2(3)...
/// k== 5
//
// merge maxArr1 and maxArr2
// and find the most max number arr
func main() {
// fmt.Println(maxNumber([]int{3, 4, 6, 5}, []int{9, 1, 2, 5, 8, 3}, 5))
// fmt.Println(maxNumber([]int{6, 7}, []int{6, 0, 4}, 5))
// fmt.Println(maxNumber([]int{4,9,5}, []int{8,7,4}, 3))
fmt.Println(maxNumber([]int{2, 5, 6, 4, 4, 0}, []int{7, 3, 8, 0, 6, 5, 7, 6, 2}, 15))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func maxNumber(nums1 []int, nums2 []int, k int) []int {
answer := make([]int, k)
for i := max(0, k-len(nums2)); i <= len(nums1) && i <= k; i++ {
a1 := maxArr(nums1, i)
a2 := maxArr(nums2, k-i)
merged := merge(a1, a2, k)
for p := 0; p < k; {
if merged[p] == answer[p] {
p++
} else {
if merged[p] > answer[p] {
answer = merged
}
break
}
}
}
return answer
}
func greater(num1 []int, i int, num2 []int, j int) bool {
for i < len(num1) && j < len(num2) && num1[i] == num2[j] {
i++
j++
}
return j == len(num2) || (i < len(num1) && num1[i] > num2[j])
}
func merge(num1 []int, num2 []int, k int) []int {
anwser := make([]int, k)
// 603
// 9820 9 8 6 2 0 3 (0)
// | 9820
// 9:6 9
// 8:6 8
// 0(top):2 2
// 0(top):0(bottom) 0 top, why 0 at top?
// next of top 0 is 3 is great bottom
for i, j, r := 0, 0, 0; r < k; r++ {
if greater(num1, i, num2, j) {
anwser[r] = num1[i]
i++
} else {
anwser[r] = num2[j]
j++
}
}
return anwser
}
func maxArr(nums []int, n int) []int {
stack := make([]int, n)
size := 0
for i := 0; i < len(nums); i++ {
// size
// 5 3, 8
for len(nums)-i > n-size && size > 0 && nums[i] > stack[size-1] {
size--
}
if size < n {
stack[size] = nums[i]
size++
}
}
return stack
}