按升序排序堆栈？

Question

按升序排序堆栈的最佳方法是什么？我遇到了这个面试问题,我遇到了一些问题,以获得最佳和最有效的解决方案.

我能想到两种方法.

1. 弹出堆栈的所有内容并将它们存储在一个数组中,然后对数组进行排序
   O(nLog n),然后将内容推回堆栈.不是最好的方式....

2. 执行堆栈的递归实现以对其进行排序

void sort(stack)
{
    type x;

    if (!isEmpty(stack)) {
        x = pop(stack);
        sort(stack);
        insert(x, stack);
    }           
}

void insert(x, stack)
{
    type y;

    if (!isEmpty(stack) && top(stack) < x) {
        y = pop(stack);
        insert(x, stack);
        push(y, stack);
    } 
    else {
        push(x, stack);
    }
} 

但是第二种方法似乎是进行了太多的递归调用,如果堆栈真的很大,那么开销将是一个问题.

是否有可能以更好的方式解决这个问题,以获得最佳的空间和时间复杂度？

有很多递归调用(重叠的子问题),这是一个dynamic programming问题类型的竞争者吗？

解决这个问题的最佳方法是什么？？

Answer 1

这是一个堆栈。除了最高值之外，您看不到任何内容。您必须将所有内容至少弹出一次，并将所有内容至少推送一次。第一种方法很好。

如果堆栈操作成本很高，但有时间期限，请在弹出时使用插入排序，并且可以在最后一次弹出完成后立即推送。但你说这是用 C++ 编写的，所以我怀疑我们是否正在考虑这样的场景。