Stack Basics

// Stack is a slice used as a pile of plates: push and pop only touch the end.
type Stack[T any] struct{ items []T }

func (s *Stack[T]) Push(v T) { s.items = append(s.items, v) }
func (s *Stack[T]) Len() int { return len(s.items) }
func (s *Stack[T]) Peek() T  { return s.items[len(s.items)-1] }
func (s *Stack[T]) Pop() T {
	v := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return v
}

// MinStack (LeetCode 155): every element remembers the minimum at the time it was pushed,
// so after a pop the previous minimum is simply the new top.
type MinStack struct{ items []struct{ val, min int } }

func (m *MinStack) Push(v int) {
	lo := v
	if n := len(m.items); n > 0 && m.items[n-1].min < lo {
		lo = m.items[n-1].min
	}
	m.items = append(m.items, struct{ val, min int }{v, lo})
}
func (m *MinStack) Pop()        { m.items = m.items[:len(m.items)-1] }
func (m *MinStack) Top() int    { return m.items[len(m.items)-1].val }
func (m *MinStack) GetMin() int { return m.items[len(m.items)-1].min }

// EvalRPN (LeetCode 150): "3 4 +" puts the operator AFTER its operands, so operands wait on a stack.
func EvalRPN(tokens []string) int {
	var st Stack[int]
	for _, t := range tokens {
		switch t {
		case "+", "-", "*", "/":
			b, a := st.Pop(), st.Pop() // the FIRST pop is the right-hand operand
			switch t {
			case "+":
				st.Push(a + b)
			case "-":
				st.Push(a - b)
			case "*":
				st.Push(a * b)
			default:
				st.Push(a / b) // Go truncates toward zero, as the problem requires
			}
		default:
			n, _ := strconv.Atoi(t)
			st.Push(n)
		}
	}
	return st.Pop()
}

// GeneratePar (LeetCode 22): build the string one character at a time.
// Rule 1: you may add "(" while some are left. Rule 2: you may add ")" only if it closes an open one.
func GeneratePar(n int) []string {
	var out []string
	var build func(cur []byte, open, close int)
	build = func(cur []byte, open, close int) {
		if len(cur) == 2*n {
			out = append(out, string(cur))
			return
		}
		if open < n {
			build(append(cur, '('), open+1, close)
		}
		if close < open {
			build(append(cur, ')'), open, close+1)
		}
	}
	build(nil, 0, 0)
	return out
}

// CarFleet (LeetCode 853): sort by position, nearest the target first, and compute each car's arrival time.
// A car behind can never pass, so if it would arrive sooner than the fleet ahead it catches up and joins it.
// Only a car that arrives LATER than every fleet ahead leads a new fleet.
func CarFleet(target int, position, speed []int) int {
	idx := make([]int, len(position))
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(a, b int) bool { return position[idx[a]] > position[idx[b]] })
	fleets := 0
	slowest := 0.0
	for _, i := range idx {
		t := float64(target-position[i]) / float64(speed[i])
		if t > slowest { // arrives after everything ahead: cannot catch up, starts a new fleet
			fleets++
			slowest = t
		}
	}
	return fleets
}