Leetcode 堆书作业

Question

我在去年 11 月的编码面试中遇到了一个问题，需要一些帮助来找出解决该问题的最佳方法。 到目前为止我在leetcode中解决了100medium！但还是想不出答案...

问题： 给你

n

类型的书籍和一个数组

orders

代表需要删除书籍的顺序。 书籍只能垂直堆叠，并且每种类型的书籍必须成对堆叠。因此

orders.length

是 2n。只能移除书的顶部。 目标是返回按照订单数组中指定的确切顺序删除书籍所需的最小努力。

抱歉解释不好。以下详细信息更有帮助。

详情： 如果

n = 3

，书籍可以按照

[1,1,2,2,3,3], [2,2,3,3,1,1], [3,3,2,2,1,1], [1,1,3,3,2,2], [2,2,1,1,3,3] or [3,3,1,1,2,2]

这样的顺序堆放。 例如，给定

n = 3

和

orders = [3,1,2,2,1,3]

，如果我们将书堆叠为 [2,2,1,1,3,3]：（书的顶部是 3。） 我们可以毫不费力地立即删除第一本书 3 (

orders[0]

)。剩余的堆栈是[2,2,1,1,3]。 接下来，我们需要删除 1 (

orders[1]

)。由于1不在顶部，所以我们首先需要移除3，然后我们可以移除1并再次重新进货3。这需要 1 努力（仅用于移除，不考虑补货）。剩余的堆栈是[2,2,1,3]。 我们对订单数组的其余部分继续此过程，始终尝试最小化到达下一本书所需的工作量。

问题： 我怎样才能解决这个问题以最小化总工作量？ 我怎样才能知道书架，从而最大限度地减少总工作量？ -> 贪婪？ 我不确定如何解决这个问题。任何建议或解决方案将不胜感激！ 优先队列？堆栈、队列、LiknedHashMap？只是数组？

约束条件为 n <= 10^5 orders.length <= 2*10^5

我认为最小的努力是上面例子中的 6。

[2,2,3,3,1,1], [3,3,2,2,1,1] and whatever

有同样的努力，6.
因此它可能非常简单。 所以在我看来，贪婪的人适合它。按照给定的顺序堆叠书籍对。 如果订单是 [

3

,

1

,

2

,1,2,3]，则只需堆叠 3,3，然后堆叠 3,3,1,1，然后堆叠 3,3,1,1,2,2。 我无法证明这一点，但我认为这是最好的方法。我说得对吗？

Answer 1

在研究了Fenwick Tree和Segment tree之后，然后得到@wLui155的提示，我通过Fenwick Tree和HashMap解决了这个问题。花了1年时间才解决。哇…我意识到像栈、队列、linkedList这样的基本数据结构不足以通过真正的代码评估！

    public int books(int[] orders, int n) {
        // shelf is Fenwick Tree that starts from node 1.
        int[] shelf = new int[n + 1];
        // [bookType, index in tree]
        HashMap<Integer, Integer> map = new HashMap<>();
        int i = 1;
        for (int book : orders) {
            if (!map.containsKey(book)) {
                shelf[i] = 2;
                map.put(book, i);
                i++;
            }
            // Just for efficiency.
            if (i == n + 1) break;
        }
        // The book on top of the shelf needs no effort.
        shelf[map.get(orders[0])] = 0;
        build(shelf);

        int sum = 0;
        for (int book : orders) {
            int index = map.get(book);
            sum += query(shelf, index);
            // Removing a book has a effect on only behind for that book index.
            update(shelf, index + 1, -1);
        }
        return sum;
    }

    private void build(int[] shelf) {
        for (int i = 1; i < shelf.length; i++) {
            int j = i + lsb(i);
            if (j < shelf.length) shelf[j] += shelf[i];
        }
    }

    private void update(int[] shelf, int idx, int delta) {
        while (idx < shelf.length) {
            shelf[idx] += delta;
            idx += lsb(idx);
        }
    }

    private int query(int[] shelf, int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += shelf[idx];
            idx -= lsb(idx);
        }
        return sum;
    }

    private int lsb(int i) {
        return i & -i;
    }
    ```