arrays - 日常编码问题 260 : Reconstruct a jumbled array - Intuition?

Question

我正在回答下面的问题。

序列 [0, 1, ..., N] 被打乱了，你对它的顺序的唯一线索是一个数组，表示每个数字是大于还是小于最后一个。给定这些信息，重建一个与其一致的数组。

例如，给定 [None, +, +, -, +]，您可以返回 [1, 2, 3, 0, 4]。

我在 this post 上完成了解决方案但仍然无法理解为什么这个解决方案有效。如果我在面试时把它摆在我面前，我认为我无法想出解决方案。谁能解释一下它背后的直觉？提前致谢!

Answer 1

它起作用是因为所有的变化都是连续的，要么加一，要么减一，从同一个地方开始增加和减少序列。这保证了我们总体上有一个顺序列表。例如，给定任意

[None, +, -, +, +, -]

为方便起见垂直翻转，我们可以看到

None   0
+      1
-     -1
+      2
+      3
-     -2

现在只需将它们向上移动两个(以考虑 -2):

2 3 1 4 5 0
 + - + + -