NGN（Next Greater Number）是一种有趣的算法问题，用下面的问题来理解下：
指定一个数组，要求返回一个等长的数组，对应索引存储着下一个更大的元素，如果没有更大的元素，就返回-1。 如给定数组 [2,1,9,3,7,4]，需返回 [9,9,-1,7,-1,-1] 第0个元素2后面下一个更大的元素为9，第1个元素1后面更大的元素为9，第2个元素9后面没有更大的元素，第4个元素3后面更大元素为7，第5个元素7后面没有更大元素，第6个元素后没有更大元素。
要解决这种问题，容易想到的是暴力查找，使用两层循环，外层循环遍历数组，内存循环查找下一个更大的数，如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func ngn(data []int) []int {
result := make([]int, len(data))
for idx, n := range data {
nextGreaterNum := -1
for i := idx + 1; i < len(data); i++ {
if data[i] > nextGreaterNum && data[i] > n {
nextGreaterNum = data[i]
}
}
result[idx] = nextGreaterNum
}
return result
}
这种方法时间复杂度较高，为 \(O(n^2)\)。
处理这种问题，有一种特定的解决技巧，就是使用单调栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func ngn(data []int) []int {
result := make([]int, len(data))
s := NewStack()
for i := len(data) - 1; i >= 0; i-- {
for s.Size() != 0 && s.Top() <= data[i] {
// 栈去掉比 data[i] 小的元素，只留下比 data[i] 大的元素
s.Pop()
}
if s.Size() == 0 {
// 栈已空，没有比 data[i] 大的元素了
result[i] = -1
} else {
// 栈非空，栈顶即是 data[i] 的Next greater number
result[i] = s.Top()
}
// 逆序入栈，出栈的时候即是正序了
s.Push(data[i])
}
return result
}
时间复杂度 O(n)。
上面的是普通的典型问题，对于下面的变型也可以用单调栈解决：
给定一个循环数组，返回每个元素的下一个更大的数的索引组成的数组。 如给定数组 [5,1,9,3,7,4]，应该返回 [2,2,-1,4,2,0]。
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
func ngn(data []int) []int {
dataSize := len(data)
result := make([]int, dataSize)
s := NewStack()
// 将原数组长度翻倍，以模拟循环效果
for i := 2*dataSize - 1; i >= 0; i-- {
idx := i % dataSize
for s.Size() != 0 && data[s.Top()] <= data[idx] {
s.Pop()
}
if s.Size() == 0 {
result[idx] = -1
} else {
result[idx] = s.Top()
}
s.Push(idx)
}
return result
}
func main() {
var a = []int{5, 1, 9, 3, 7, 4}
r := ngn(a)
// [2 2 -1 4 2 0]
fmt.Println(r)
}