155.go 1.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
  1. package main
  2. import (
  3. "fmt"
  4. )
  5. type MinStackOld struct {
  6. val []int
  7. min []int
  8. top int
  9. }
  10. /** initialize your data structure here. */
  11. func ConstructorOld() MinStackOld {
  12. s := MinStackOld{make([]int, 0), make([]int, 0), -1}
  13. return s
  14. }
  15. func (this *MinStackOld) Push(x int) {
  16. this.val = append(this.val, x)
  17. this.top++
  18. idx := 0
  19. for ; idx < this.top; idx++ {
  20. if x > this.val[idx] {
  21. break
  22. }
  23. }
  24. this.min = append(this.min, 0)
  25. copy(this.min[idx+1:this.top+1], this.min[idx:this.top])
  26. this.min[idx] = x
  27. }
  28. func (this *MinStackOld) Pop() {
  29. if this.top != -1 {
  30. idx := 0
  31. for ; idx < this.top+1; idx++ {
  32. if this.min[idx] == this.val[this.top] {
  33. break
  34. }
  35. }
  36. this.min = append(this.min[:idx], this.min[idx+1:]...)
  37. this.val = this.val[:this.top]
  38. this.top--
  39. }
  40. }
  41. func (this *MinStackOld) Top() int {
  42. return this.val[this.top]
  43. }
  44. func (this *MinStackOld) GetMin() int {
  45. return this.min[this.top]
  46. }
  47. /**
  48. * Your MinStack object will be instantiated and called as such:
  49. * obj := Constructor();
  50. * obj.Push(x);
  51. * obj.Pop();
  52. * param_3 := obj.Top();
  53. * param_4 := obj.GetMin();
  54. */
  55. type MinStack struct {
  56. val []int
  57. min []int
  58. }
  59. /** initialize your data structure here. */
  60. func Constructor() MinStack {
  61. return MinStack{}
  62. }
  63. // important! min []int stores the "current miximum"
  64. func (this *MinStack) Push(x int) {
  65. this.val = append(this.val, x)
  66. if len(this.min) == 0 {
  67. this.min = append(this.min, x)
  68. return
  69. }
  70. m := this.min[len(this.min)-1]
  71. if x < m {
  72. this.min = append(this.min, x)
  73. return
  74. }
  75. this.min = append(this.min, m)
  76. }
  77. func (this *MinStack) Pop() {
  78. n := len(this.val) - 1
  79. this.val = this.val[:n]
  80. this.min = this.min[:n]
  81. }
  82. func (this *MinStack) Top() int {
  83. return this.val[len(this.val)-1]
  84. }
  85. func (this *MinStack) GetMin() int {
  86. return this.min[len(this.min)-1]
  87. }
  88. func main() {
  89. stack := Constructor()
  90. stack.Push(1)
  91. fmt.Println(stack.Top())
  92. fmt.Println(stack.GetMin())
  93. }