首页 > 代码库 > 桟的min实现：O(1)时间复杂度
桟的min实现：O(1)时间复杂度
实现桟的push和pop操作，以及桟的min操作返回桟中的最小值，要求这三个操作的时间复杂度均为O(1)。
在Java中可以使用LinkedList实现桟的各种操作，这里使用双向链表实现桟的push和pop操作，这两个操作都能维持O(1)的时间复杂度，但是对于求桟中元素的最小值，最容易想到的方法是遍历整个桟，然后返回，但此时的时间复杂度为O(n)，要想省下时间复杂度，则必须牺牲空间复杂度，所以可以再维护一个和桟大小相同的数据结构（可以是链表，动态数组或者一个新的桟）来存储每个元素入桟之后对应的桟中的最小元素，在对桟执行push和pop操作时，这个数据结构也跟着变化，这样就能以O(1)的时间复杂度实现min操作了。
public class Stack1<Key extends Comparable<Key>> { private Node top; private Node minTop; private class Node { Key key; Node next; Node prev; Node(Key key, Node next, Node prev) { this.key = key; this.next = next; this.prev = prev; } } /* 元素入桟,因为要求桟的push,pop以及min操作都为O(1)操作，所以 * 在元素入桟时还要维护一个min桟 */ public void push(Key key) { if (top == null) { top = new Node(key, null, null); top.next = null; top.prev = null; pushMin(key); return; } Node x = new Node(key, null, top); top.next = x; top = x; pushMin(key); } /* 维护一个最小元素的桟 */ private void pushMin(Key key) { if (minTop == null) { minTop = new Node(key, null, null); minTop.next = null; return; } if (key.compareTo(minTop.key) < 0) { Node x = new Node(key, null, minTop); minTop.next = x; minTop = x; } else { Node x = new Node(minTop.key, null, minTop); minTop.next = x; minTop = x; } } /* 元素出桟，因为要求桟的push,pop以及min操作都为O(1)操作，所以 * 在元素入桟时还要维护一个min桟 */ public Key pop() { if (top == null) { return null; } Key key = top.key; if ((top.prev == null) && (top.next == null)) { top = null; popMin(); return key; } top = top.prev; top.next = null; popMin(); return key; } /* 返回桟中的最小元素 */ private Key popMin() { if (minTop == null) { return null; } Key key = minTop.key; if ((minTop.prev == null) && (minTop.next == null)) { minTop = null; return key; } minTop = minTop.prev; minTop.next = null; return minTop.key; } /* 返回桟的最小元素 */ public Key min() { /* 注意边界条件，当维护的桟为空时minTop也为空 */ if (minTop == null) { return null; } return minTop.key; } public static void main(String[] args) { Stack1<Integer> stack1 = new Stack1<Integer>(); stack1.push(11); stack1.push(23); stack1.push(4); stack1.push(76); stack1.push(13); stack1.push(42); System.out.println(stack1.min() + " " + stack1.pop()); System.out.println(stack1.min() + " " + stack1.pop()); System.out.println(stack1.min() + " " + stack1.pop()); System.out.println(stack1.min() + " " + stack1.pop()); System.out.println(stack1.min() + " " + stack1.pop()); System.out.println(stack1.min() + " " + stack1.pop()); System.out.println(stack1.min() + " " + stack1.pop()); }}
上面main函数的输出为：
4 424 134 764 411 2311 11null null
桟的min实现：O(1)时间复杂度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。