未分類

Next Greater Element I

Next Greater Element I

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

1
2
3
4
5
6
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

1
2
3
4
5
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

  1. All elements in nums1 and nums2 are unique.
  2. The length of both nums1 and nums2 would not exceed 1000.
提示 解題應用
Stack 未使用Stack直接做判斷

Default:

1
2
3
func nextGreaterElement(findNums []int, nums []int) []int {
}

解答思路:

這邊我直接判斷,也就是說第一個陣列拿到的值到第二個陣列開始判斷,並在第二個陣列找到與第一個陣列所取出的值相同才開始找比其大的值,若遍歷到底都沒有才回傳-1,並且不斷重覆上述動作直到第一個陣列所有元素後頭的最大值都找到為止,雖然這麼做相當簡單但費時,不過目前尚未想到更好的辦法。

程式碼解說:

一開始先利用回圈從第一個陣列取出目標,接著與巢狀迴圈取出的第二個陣列值進行比較,如果在第二個陣列中發現的目標值,註記之後此時才開始需要比目標值還大的值,如果發現了比其大的值就放入結果之中同時將註記改回false,而當巢狀迴圈遍歷結束後但註記仍為true的話,表示沒發現後頭有比其更大的值,因此才再結果之中放入-1,最後直到第一個陣列所有元素後頭的最大值都找到才回傳結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var find bool
var result []int
for _, target := range findNums {
for _, num := range nums {
if num == target {
find = true
}
if find && num > target {
result = append(result, num)
find = false
break
}
}
if find {
result = append(result, -1)
find = false
}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func nextGreaterElement(findNums []int, nums []int) []int {
var find bool
var result []int
for _, target := range findNums {
for _, num := range nums {
if num == target {
find = true
}
if find && num > target {
result = append(result, num)
find = false
break
}
}
if find {
result = append(result, -1)
find = false
}
}
return result
}

總結:

因為目前尚未想到更好的辦法,所以直接用了最簡單但費時的方法,第一個陣列拿到的值到第二個陣列開始判斷,並在第二個陣列找到與第一個陣列所取出的值相同才開始找比其大的值,若遍歷到底都沒有才回傳-1,並且不斷重覆上述動作直到第一個陣列所有元素後頭的最大值都找到為止。

分享到