2022-11-11:设计一个最大栈数据结构,既支持栈操作,又支持查找栈中最大元素。 实现 MaxStack

2022-11-11:设计一个最大栈数据结构,既支持栈操作,又支持查找栈中最大元素。
实现 MaxStack 类:
MaxStack() 初始化栈对象
void push(int x) 将元素 x 压入栈中。
int pop() 移除栈顶元素并返回这个元素。
int top() 返回栈顶元素,无需移除。
int peekMax() 检索并返回栈中最大元素,无需移除。
int popMax() 检索并返回栈中最大元素,并将其移除。
如果有多个最大元素,只要移除 最靠近栈顶 的那个。

答案2022-11-11:

加强堆+双向链表。
代码没时间写,将就一下吧。

代码用java编写。代码如下:

public class Code03_MaxStack {

    class MaxStack {

        public int cnt;

        public HeapGreater<Node> heap;

        public Node top;

        public MaxStack() {
            cnt = 0;
            heap = new HeapGreater<>(new NodeComparator());
            top = null;
        }

        public void push(int x) {
            Node cur = new Node(x, ++cnt);
            heap.push(cur);
            if (top == null) {
                top = cur;
            } else {
                top.last = cur;
                cur.next = top;
                top = cur;
            }
        }

        public int pop() {
            Node ans = top;
            if (top.next == null) {
                top = null;
            } else {
                top = top.next;
                top.last = null;
            }
            heap.remove(ans);
            return ans.val;
        }

        public int top() {
            return top.val;
        }

        public int peekMax() {
            return heap.peek().val;
        }

        public int popMax() {
            Node ans = heap.pop();
            if (ans == top) {
                if (top.next == null) {
                    top = null;
                } else {
                    top = top.next;
                    top.last = null;
                }
            } else {
                if (ans.next != null) {
                    ans.next.last = ans.last;
                }
                if (ans.last != null) {
                    ans.last.next = ans.next;
                }
            }
            return ans.val;
        }

        class Node {
            public int val;
            public int cnt;
            public Node next;
            public Node last;

            public Node(int v, int c) {
                val = v;
                cnt = c;
            }
        }

        class NodeComparator implements Comparator<Node> {

            @Override
            public int compare(Node o1, Node o2) {
                return o1.val != o2.val ? (o2.val - o1.val) : (o2.cnt - o1.cnt);
            }

        }

        class HeapGreater<T> {

            private ArrayList<T> heap;
            private HashMap<T, Integer> indexMap;
            private int heapSize;
            private Comparator<? super T> comp;

            public HeapGreater(Comparator<? super T> c) {
                heap = new ArrayList<>();
                indexMap = new HashMap<>();
                heapSize = 0;
                comp = c;
            }

            public T peek() {
                return heap.get(0);
            }

            public void push(T obj) {
                heap.add(obj);
                indexMap.put(obj, heapSize);
                heapInsert(heapSize++);
            }

            public T pop() {
                T ans = heap.get(0);
                swap(0, heapSize - 1);
                indexMap.remove(ans);
                heap.remove(--heapSize);
                heapify(0);
                return ans;
            }

            public void remove(T obj) {
                T replace = heap.get(heapSize - 1);
                int index = indexMap.get(obj);
                indexMap.remove(obj);
                heap.remove(--heapSize);
                if (obj != replace) {
                    heap.set(index, replace);
                    indexMap.put(replace, index);
                    resign(replace);
                }
            }

            private void resign(T obj) {
                heapInsert(indexMap.get(obj));
                heapify(indexMap.get(obj));
            }

            private void heapInsert(int index) {
                while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
                    swap(index, (index - 1) / 2);
                    index = (index - 1) / 2;
                }
            }

            private void heapify(int index) {
                int left = index * 2 + 1;
                while (left < heapSize) {
                    int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1)
                            : left;
                    best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
                    if (best == index) {
                        break;
                    }
                    swap(best, index);
                    index = best;
                    left = index * 2 + 1;
                }
            }

            private void swap(int i, int j) {
                T o1 = heap.get(i);
                T o2 = heap.get(j);
                heap.set(i, o2);
                heap.set(j, o1);
                indexMap.put(o2, i);
                indexMap.put(o1, j);
            }

        }

    }

}

左神java代码

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!