Leetcode叠书面试题：最小移除代价与最优堆叠策略求解

去年11月的编程面试中遇到一道算法题，目前已刷完100道Leetcode中等题，但仍无法想出解法，特此求助。

题目描述 #

给定n种书籍，以及表示书籍移除顺序的数组orders。书籍仅能垂直堆叠，且每种书必须成对堆叠（因此orders.length为2n），仅可移除栈顶书籍。目标是返回按orders指定顺序移除书籍所需的最小总代价。

补充说明 #

以n=3为例，合法堆叠顺序如[1,1,2,2,3,3]等6种。给定n=3、orders=[3,1,2,2,1,3]，若堆叠为[2,2,1,1,3,3]（栈顶为3）：

• 可直接移除orders[0]的3，无代价，剩余栈为[2,2,1,1,3]；
• 需移除orders[1]的1，因1不在栈顶，需先移除3（代价+1），移除1后再放回3，剩余栈为[2,2,1,3]；
  后续按此流程处理，需始终最小化每一步代价。

核心问题 #

• 如何求解最小总代价？
• 如何确定最优堆叠顺序？
• 是否可用贪心算法？
• 应选用栈、优先队列还是其他数据结构？

约束条件 #

• n≤10^5
• orders.length≤2*10^5

个人猜测 #

我认为上述示例的最小代价为6，多种堆叠顺序代价均为6。我猜测按orders中出现的顺序成对堆叠是最优策略，但无法证明，该思路是否正确？

内容的提问来源于stack exchange，提问作者foylee