算法—递归逆序栈、排序栈

1. 递归逆序栈

• 只用递归逆序一个栈，时间复杂度O(n^2)

// 栈底元素移除掉，上面的元素盖下来
// 返回移除掉的栈底元素
public static int bottomOut(Stack<Integer> stack) {
	int ans = stack.pop();
	if (stack.isEmpty()) {
		return ans;
	} else {
		int last = bottomOut(stack);
		stack.push(ans);
		return last;
	}
}

public static void reverse(Stack<Integer> stack) {
	if (stack.isEmpty()) {
		return;
	}
	int num = bottomOut(stack);
	reverse(stack);
	stack.push(num);
}

2. 递归排序栈

• 只用递归排序一个栈，时间复杂度O(n^2)

1. a递归统计栈的深度
2. b递归到底，返回最大值
3. c递归传入深度和最大值，返回最大值个数n
4. d递归传入深度、最大值和其个数n，让这n个最大值沉底，其他数相对次序不变
5. b递归到此时深度（上次深度-n），返回此时最大值
6. …

a方法只调用一次，然后不断复用b、c、d

// 总逻辑 调用下方四个递归函数
public static void sort(Stack<Integer> stack) {
	int deep = deep(stack);
	while (deep > 0) {
		int max = max(stack, deep);
		int k = times(stack, deep, max);
		down(stack, deep, max, k);
		deep -= k;
	}
}

// 返回栈的深度
// 不改变栈的数据状况
public static int deep(Stack<Integer> stack) {
	if (stack.isEmpty()) {
		return 0;
	}
	int num = stack.pop();
	int deep = deep(stack) + 1;
	stack.push(num);
	return deep;
}

// 从栈当前的顶部开始，往下数deep层
// 返回这deep层里的最大值
public static int max(Stack<Integer> stack, int deep) {
	if (deep == 0) {
		return Integer.MIN_VALUE;
	}
	int num = stack.pop();
	int restMax = max(stack, deep - 1);
	int max = Math.max(num, restMax);
	stack.push(num);
	return max;
}

// 从栈当前的顶部开始，往下数deep层，已知最大值是max了
// 返回，max出现了几次，不改变栈的数据状况
public static int times(Stack<Integer> stack, int deep, int max) {
	if (deep == 0) {
		return 0;
	}
	int num = stack.pop();
	int restTimes = times(stack, deep - 1, max);
	// 当前的数是最大值 则times + 1
	int times = restTimes + (num == max ? 1 : 0);
	stack.push(num);
	return times;
}

// 从栈当前的顶部开始，往下数deep层，已知最大值是max，出现了k次
// 请把这k个最大值沉底，剩下的数据状况不变
public static void down(Stack<Integer> stack, int deep, int max, int k) {
	if (deep == 0) {
		// 核心代码：此时栈空，压入k个最大值
		for (int i = 0; i < k; i++) {
			stack.push(max);
		}
	} else {
		int num = stack.pop();
		down(stack, deep - 1, max, k);
		// 是最大值 不做操作 直接返回
		if (num != max) {
			stack.push(num);
		}
	}
}