golang 代码实现单调栈-526互联

有种特殊的栈，叫做单调栈，顾名思义就是栈底到栈顶呈现单调特性，比如对于列表：[]int{6, 10, 3, 7, 4, 12}，如果要实现单调栈，并不是所有入栈后呈降序或升序排列就是单调栈，如单调递增栈：

6 | 栈空，入栈 | [6]
10 | 10 > 6, 符合递增，入栈 | [6, 10]
3 | 3 < 10, 先全部出栈，把3入栈 | [3]
7 | 7 > 3, 符合递增，入栈 | [3, 7]
4 | 4 < 7, 7出栈，4入栈 | [3, 4]
12 | 12 > 4, 入栈 | [3, 4, 12]

所以最后的单调递增栈：[]int{3, 4, 12}

相应的 golang 实现:

// 单调递增栈，栈底: min, 栈顶: max
func leftMinRightMax(nums []int) []int {
	monotoneStack := []int{}
	res := make([]int, len(nums))

	for i, num := range nums {
		if len(monotoneStack) == 0 {
			monotoneStack = append(monotoneStack, num)
			res[i] = -1
		} else {
			for len(monotoneStack) > 0 && num < monotoneStack[len(monotoneStack)-1] {
				monotoneStack = monotoneStack[:len(monotoneStack)-1]
				if len(monotoneStack) > 0 {
					res[i] = monotoneStack[len(monotoneStack)-1]
				} else {
					res[i] = -1
				}
			}
			monotoneStack = append(monotoneStack, num)
		}
	}

	fmt.Println("res: ", res)
	return monotoneStack
}

根据单调递增栈的特性，给出单调递减栈的代码实现：

// 单调递减栈，栈底: max, 栈顶: min
func leftMaxRightMin(nums []int) []int {
	monotoneStack := []int{}
	res := make([]int, len(nums))

	for i, num := range nums {
		if len(monotoneStack) == 0 {
			monotoneStack = append(monotoneStack, num)
			res[i] = -1
		} else {
			for len(monotoneStack) > 0 && num > monotoneStack[len(monotoneStack)-1] {
				monotoneStack = monotoneStack[:len(monotoneStack)-1]
			}
			if len(monotoneStack) > 0 {
				res[i] = monotoneStack[len(monotoneStack)-1]
			} else {
				res[i] = -1
			}
			monotoneStack = append(monotoneStack, num)
		}
	}

	fmt.Println("res: ", res)
	return monotoneStack
}