查找堆栈数量最多只使用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，访问数据的唯一途径，也改变栈），我们必须考虑到，“日e栈应该不变“的限制意味着我们必须在完成后将其恢复到原始状态。

我们可以通过使用方法的另一组由雷蒙德赫廷杰建议去做：

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)操作中给出堆栈中的最大数量，但代价为extra space。我会给你后一种解决方案。

您需要做的就是拥有一个extra stack，该堆栈的最大元素位于顶部，用于堆栈的任何配置。

1. 当你按下一个号码给您原来的堆栈，请执行下列操作为max_stack，比较max_stack顶部的当前值和推动更大的一个在其上。
2. 当你取出了一些简单的流行从max_stack
3. 最上面的号码当你需要找出max值随便挑栈顶从max_stack。

这样你就可以获得O(1)时间内的最大数字，而推动和弹出操作也仍然是O(1)。我可以给你代码，但没有什么内容，因为它很简单。例如，如果您在订单

5 - 2 - 6 - 8 - 1

max_stack推下面的数字将包含

5 - 5 - 6 - 8 - 8

，并为您pop号码的当前max将在顶部。

我希望解决方案很明确。