按升序对堆栈进行排序？
按升序对堆栈进行排序的最佳方法是什么？我遇到了这个面试问题，我遇到了一些问题，需要最好、最有效的解决方案。
我能想到的方法有两种。
将栈中的所有内容弹出并存储到数组中，然后对数组进行排序
O(nLog n)然后将内容推回堆栈。不是最好的方法....执行堆栈的递归实现来对其进行排序
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);
}
}
但是第二种方法似乎进行了太多的递归调用和开销如果堆栈非常大，就会出现问题。
是否有可能以更好的方式解决这个问题，以获得最佳的空间和时间复杂度？
有如此多的递归调用（重叠子问题），这是动态编程类型问题的竞争者吗？
解决这个问题的最佳方法是什么？ ？
What is the best method for sorting a stack in ascending order? I came across this interview question, and I was running into some problems for the best and most efficient solution.
There are two methods that I can think of.
To pop all the contents of the stack and store them in an array, and then sort the array in
O(nLog n)and then push the contents back the stack. Not the best way....Do the recursive implementation of the stack for sorting it
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);
}
}
But the 2nd method seems to be making too many recursive calls and the overhead will be a problem if the stack happens to be really big.
Is it possible to solve this problem in a much better way for the best space and time complexity?
There are so many recursive calls, (overlapping subproblems), is this a contender for dynamic programming type of problems?
What would be the best way to solve this? ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这是一个堆栈。除了最高值之外，您看不到任何内容。您必须将所有内容至少弹出一次，并将所有内容至少推送一次。第一种方法很好。
如果堆栈操作成本很高，但有时间期限，请在弹出时使用插入排序，并且可以在最后一次弹出完成后立即推送。但你说这是用 C++ 编写的，所以我怀疑我们是否正在考虑这样的场景。
It's a stack. You can't see anything but the top value. You'll have to pop everything at least once, and push everything at least once. The first method is fine.
If the stack operations are expensive but you have a time deadline, use insertion sort as you're popping and you can push as soon as your last pop is done. But you're saying this is in C++ so I doubt we are considering such a scenario.
您可以通过消除递归来解决。为此，您只需使用一个循环在堆栈下迭代，直到堆栈为空。
例如伪代码：
You can solve by eliminating the recursion. For this you just use a loop iterating under a stack until it is empty.
For example, pseudo code:
这个问题的复杂度不能小于 O(n^2)。如需进一步参考，请参阅此处
This problem cant have complexity less than O(n^2). For further reference refer here