Algs4-2.4.2分析使用栈或队列在常数时间内找到最大元素

2.4.2分析以下说法:要实现在常数时间找到最大元素,为何不用一个栈或队列,然后记录已插入的最大元素并在找出最大元素时返回 它的值?
答:如果只是找出一个最大元素,遍历所有元素记录最大者即可,没有必要再花一个栈或队列的空间来存储这些元素。
如果要找出最大元素后,除开这个元素后再继续找最大元素,用一个栈或队列如果采用无序方式存储所有元素并找出一个最大元素需要 遍历完所有的元素最坏界为O(n),找出所有最大元素的最坏界为O(n^2),如果要保持栈或队列中元素的有序性最坏界为O(n^2)找出最大 元素要O(1)。元素过多时也无法一次性存储在内存中。
原文地址:https://www.cnblogs.com/longjin2018/p/9868601.html