堆栈以 O(N) 排序

Question

我正在创建一种方法来测试给定堆栈是否已排序。我已经完成了程序的主要任务，但是有没有办法在没有 O(N^2) 的情况下实现这个算法。我想用 O(N) 得到这个。这样的解决方案存在吗？如果是这样，有人可以指出我正确的方向。

一些规则 - 只能制作一个辅助堆叠。 - 没有额外的数据结构。 - 如果堆栈为空或只有一个项目，则假定它已排序。 - 必须在 O(N)

内执行

public static boolean isSorted(Stack s){

    boolean sorted = true;
    Stack backup = new Stack();

    int prev, curr;

    if(s.isEmpty() || s.size() == 1) {

        sorted = true;  

    } else {

        while(!s.isEmpty()){

            prev = s.pop();
            backup.push(prev);

            curr = s.pop();
            backup.push(curr);

            if(prev > curr && sorted)
                sorted = false;

        }

    }

    while(!backup.isEmpty()) {
        s.push(backup.pop());
    }


    return sorted;

}

示例输入：{20,20,17,11,9,8,3,2}

输出：

 top 2 3 8 9 11 17 20 20 bottom
| isSorted = true
| top 2 3 8 9 11 17 20 20 bottom

函数结束。给定的堆栈应该处于其原始状态。我只需要在 O(N)

中得到这个

Answer 1

您在这里提出的概念不是 O(n²)，而是 O(n) - 对于堆栈中的每个元素，您执行恒定数量的操作, 不管 N.

的大小

但是，您应该注意，这里有一个错误 - 在循环的每次迭代中，您都会弹出两个元素并比较它们，因此您只是在有效地测试每对元素是否已排序，而不是整个元素集（例如，使用值 {2, 1, 500, 400} 尝试此算法）。此外，请注意连续相等的值不会破坏排序，因此您应该使用 >= 而不是 >。另一个优化可能是一旦检测到堆栈未排序就快速失败：

public static boolean isSorted(Stack s) {

    boolean sorted = true;
    Stack backup = new Stack();

    int prev;
    int curr = Integer.MIN_VALUE;

    while (!s.isEmpty() && sorted) {
        prev = curr;
        curr = s.pop();
        backup.push(curr);
        sorted = (prev <= curr);
    }

    while (!backup.isEmpty()) {
        s.push(backup.pop());
    }

    return sorted;
}

堆栈以 O(N) 排序

Stack is sorted with O(N)

java

sorting

stack