仅使用 PUSH 和 PUSH 查找堆栈中最大的数字POP操作

Question

谁能帮我解决这个问题的算法（这是一个面试问题）：

给你一个堆栈。设计一个算法来找到最大数量 仅使用 PUSH/POP 操作。

Answer 1

鉴于原始帖子中缺乏约束，您可以弹出所有数据并计算运行最大值：

if empty(st) -> raise exception
m <- pop(st)
while not empty(st)
    n <- pop(st)
    if n > m
        m <- n

编辑（新限制是原始堆栈不变，并且第二个可用堆栈的新资源）：

if empty(st) -> raise exception
m <- pop(st)
push(alt_st, m)
while not empty(st)
    n <- pop(st)
    push(alt_st, n)
    if n > m
        m <- n
while not empty(alt_st):
    n <- pop(alt_st)
    push(st, n)

Answer 2

因为原始堆栈不能是只读的（Pop，访问数据的唯一方式，也会修改堆栈），我们必须考虑“堆栈应该不变”的限制意味着我们必须完成后将其恢复到原始状态。

我们可以通过使用 Raymond Hettinger 提出的方法中的另一个堆栈来实现：

int get_max_from_stack(Stack stack) {
    int M = stack.pop();
    Stack aux;
    aux.push(M);
    while (!stack.empty()){
        int tmp = stack.pop();
        aux.push(tmp);
        M = max(M, tmp);
    };

    while (!aux.empty())
        stack.push(aux.pop());

    return M;
};

Answer 3

有两种方法可以解决这个问题，要么你可以创建一个函数get_max来给出堆栈中的最大数字，或者你可以维护一些额外的信息，使用它可以给出堆栈中的最大数字在O(1)操作中，但以额外空间为代价。我会给你后一种解决方案。

您需要做的是拥有一个额外的堆栈，对于堆栈的任何配置，该堆栈的最大元素都位于顶部。

1. 每当您将数字推入原始堆栈时，请对 max_stack 执行以下操作，将当前值与 max_stack 的顶部进行比较，并将较大的值推入其中。
2. 当您弹出一个数字时，只需从 max_stack 中弹出最上面的数字
3. 当您需要找出 max 值时，只需从 max_stack 中选择堆栈顶部。

这样你就可以在O(1)时间内获得最大数量，并且push和pop操作也保持O(1)。我本可以给你代码，但里面没有太多内容，因为它很简单。例如，如果您按

5 - 2 - 6 - 8 - 1

的顺序推送以下数字，max_stack 将包含

5 - 5 - 6 - 8 - 8 code>

，当您弹出数字时，当前max将位于顶部。

我希望解决方案是明确的。