思路1: 维护一个最小值 MinValue，初始化为整数最大值：$2^{31}$， push 时： 如果当前值比最小值小，则更新最小值；pop 时： 遍历栈更新最小值；
type MinStack struct {
Elements []int
MinValue int
}
func Constructor() MinStack {
return MinStack{
Elements: []int{},
MinValue: (1 << 31) - 1,
}
}
func (this *MinStack) Push(val int) {
this.Elements = append(this.Elements, val)
if val < this.MinValue {
this.MinValue = val
}
}
func (this *MinStack) Pop() {
top := this.Elements[len(this.Elements)-1]
this.Elements = this.Elements[:len(this.Elements)-1]
if this.MinValue == top {
this.MinValue = (1 << 31) - 1
for _, element := range this.Elements {
if element < this.MinValue {
this.MinValue = element
}
}
}
}
func (this *MinStack) Top() int {
top := this.Elements[len(this.Elements)-1]
return top
}
func (this *MinStack) GetMin() int {
return this.MinVa思路2：用两个栈实现，一个最小栈始终保证最小值在顶部
type MinStack struct {
min []int
stack []int
}
func Constructor() MinStack {
return MinStack{
min: make([]int, 0),
stack: make([]int, 0)
}
}
func (this *MinStack) Push(val int) {
min := this.GetMin()
if val < min {
this.min = append(this.min, val)
} else {
this.min = append(this.min, min)
}
this.stack = append(this.stack, val)
}
func (this *MinStack) Pop {
if len(this.stack) == 0 {
return
}
this.stack = this.stack[:len(this.stack)-1]
this.min = this.min[:len(this.min)-1]
}
func (this *MinStack) Top() int {
if len(this.stack) == 0 {
return 0
}
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
if len(this.min) == 0 {
return 1 << 31
}
min := this.min[len(this.min)-1]
return min
}// Something worong, but i do not know.
func decodeString(s string) string {
if len(s) == 0 {
return ""
}
stack := make([]byte, 0)
for i := 0; i < len(s); i++ {
switch s[i] {
case ']':
temp := make([]byte, 0)
for len(stack) != 0 && stack[len(stack)-1] != '[' {
v := stack[len(stack)-1]
stack = stack[:len(stack)-1]
temp = append(temp, v)
}
stack = stack[:len(stack)-1]
idx := 1
for len(stack) >= idx && stack[len(stack)-idx] >= '0' && stack[len(stack)-1] <= '9' {
idx++
}
num := stack[len(stack)-idx+1:]
stack = stack[:len(stack)-idx+1]
count, _ := strconv.Atoi(string(num))
for j := 0; j < count; j++ {
for j := len(temp) - 1; j >= 0; j-- {
stack = append(stack, temp[j])
}
}
fmt.Println(string(stack))
default:
stack = append(stack, s[i])
}
}
return string(stack)
}func decodeString(s string) string {
if len(s) == 0 {
return ""
}
stack := make([]byte, 0)
for i := 0; i < len(s); i++ {
switch s[i] {
case ']':
temp := make([]byte, 0)
for len(stack) != 0 && stack[len(stack)-1] != '[' {
v := stack[len(stack)-1]
stack = stack[:len(stack)-1]
temp = append(temp, v)
}
// pop '['
stack = stack[:len(stack)-1]
// pop num
idx := 1
for len(stack) >= idx && stack[len(stack)-idx] >= '0' && stack[len(stack)-idx] <= '9' {
idx++
}
num := stack[len(stack)-idx+1:]
stack = stack[:len(stack)-idx+1]
count, _ := strconv.Atoi(string(num))
for j := 0; j < count; j++ {
for j := len(temp) - 1; j >= 0; j-- {
stack = append(stack, temp[j])
}
}
default:
stack = append(stack, s[i])
}
}
return string(stack)
}func cloneGraph(node *Node) *Node {
visited := make(map[*Node]*Node)
return clone(node, visited)
}
// 递归克隆， 传入已访问的元素为过滤条件
func clone(node *Node, visited map[*Node]*Node) *Node {
if node == nil {
return nil
}
// 已访问过的直接返回
if v, ok := visited[node]; ok {
return v
}
newNode := &Node {
Val: node.Val,
Neighbors: make([]*Node, len(node.Neighbors)),
}
visited[node] = newNode
for i :=0; i < len(node.Neighbors); i++ {
newNode.Neighbors[i] = clone(node.Neighbors[i], visited)
}
return newNode
}func numIslands(grid [][]byte) int {
var count int
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[i]); j++ {
if grid[i][j] == '1' && dfs(grid, i, j) >= 1 {
count++
}
}
}
return count
}
func dfs(grid [][]byte, i, j int) int {
if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) {
return 0
}
if grid[i][j] == '1' {
// 标记访问过的节点
grid[i][j] = 0
return dfs(grid, i-1, j) + dfs(grid, i, j-1) + dfs(grid, i+1) + dfs(grid, i, j+1) + 1
}
return 0
}func largestRectangleArea(heights []int) int {
if len(heights) == 0 {
return 0
}
stack := make([]int, 0)
maxArea := 0
for i := 0; i <= len(heights); i++ {
var cur int
if i == len(heights) {
cur = 0
} else {
cur = heights[i]
}
// 当前高度小于栈，则将栈内元素都弹出计算面积
for len(stack) > 0 && cur <= heights[stack[len(stack)-1]] {
pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]
h := heights[pop]
// 计算宽度
w := i
if len(stack) > 0 {
peak := stack[len(stack)-1]
w = i - peak - 1
}
maxArea = max(maxArea, h * w)
}
stack = append(stack, i)
}
return maxArea
}
func max(x, y int) int {
if x > y { return x}
return y
}