ThinkerQAQ

NOTE

包含min函数的栈

记录使用辅助最小值栈实现 O(1) 获取栈最小值的方法。

Data Structures & Algorithms创建于 更新于 约 1 分钟读完historical

这是历史学习笔记，可能存在过时或不完整的理解。

1. 题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

2. 思路

  • 使用额外的最小值栈

3. 实现

package main

var data []int
var minStack []int

func stackPush(stack *[]int, num int) {
	*stack = append(*stack, num)
}

func stackPop(stack *[]int) int {
	top := (*stack)[len(*stack)-1]
	*stack = (*stack)[:len(*stack)-1]
	return top
}

func stackEmpty(stack []int) bool {
	return len(stack) == 0
}

func stackTop(stack []int) int {
	return stack[len(stack)-1]
}

func Push(node int) {
	if stackEmpty(data) {
		stackPush(&data, node)
		stackPush(&minStack, node)
		return
	}

	top := stackTop(minStack)
	if top < node {
		stackPush(&minStack, top)
	} else {
		stackPush(&minStack, node)
	}
	stackPush(&data, node)
}
func Pop() {
	if stackEmpty(data) {
		return
	}
	stackPop(&minStack)
	stackPop(&data)

}
func Top() int {
	if stackEmpty(data) {
		return 0
	}
	return stackTop(data)
}
func Min() int {
	if stackEmpty(minStack) {
		return 0
	}
	return stackTop(minStack)
}

4. 参考

讨论

使用 GitHub 账号参与讨论，评论会保存在 GitHub Issues 中。在 GitHub 查看