给定一个数组，找出每个元素的下一个较小的元素
给定一个数组，find每个元素的下一个更小的元素，而不改变元素的原始顺序。
例如，假设给定的数组是4,2,1,5,3。
结果数组将是2,1，-1,3，-1。
我在一次采访中被问到了这个问题，但是我想不出比一般的O（n ^ 2）解决scheme更好的解决scheme。 任何我能想到的方法，即制作一个二叉search树，或sorting数组，都会扭曲元素的原始顺序，从而导致错误的结果。
任何帮助将不胜感激。
O（N）algorithm
- 将输出数组初始化为全-1。
- 在input数组中创build一个我们访问过的项目的空索引，但是还不知道输出数组中的答案。
- 迭代input数组中的每个元素：
- 它是否比栈顶索引的项目小？
- 是。 这是第一个这样的元素。 在我们的输出数组中填入相应的元素，从堆栈中删除项目，然后再试一次，直到堆栈为空或答案为否。
- 不，继续3.2。
- 将此索引添加到堆栈。 从3继续迭代。
- 它是否比栈顶索引的项目小？
Python实现
def find_next_smaller_elements(xs): ys=[-1 for x in xs] stack=[] for i,x in enumerate(xs): while len(stack)>0 and x<xs[stack[-1]]: ys[stack.pop()]=x stack.append(i) return ys >>> find_next_smaller_elements([4,2,1,5,3]) [2, 1, -1, 3, -1] >>> find_next_smaller_elements([1,2,3,4,5]) [-1, -1, -1, -1, -1] >>> find_next_smaller_elements([5,4,3,2,1]) [4, 3, 2, 1, -1] >>> find_next_smaller_elements([1,3,5,4,2]) [-1, 2, 4, 2, -1] >>> find_next_smaller_elements([6,4,2]) [4, 2, -1]
说明
怎么运行的
这是可行的，因为每当我们添加一个项目到堆栈中，我们知道它的值已经大于或等于堆栈中的每个元素。 当我们访问数组中的一个元素时，我们知道如果它低于堆栈中的任何一个元素，它必须低于堆栈中的最后一个元素，因为最后一个元素必须是最大的。 所以我们不需要在堆栈上进行任何search，我们可以考虑最后一个项目。
注意：只要添加最后一步来清空堆栈，并使用每个剩余索引将相应的输出数组元素设置为-1，就可以跳过初始化步骤。 在创build它时，将Python初始化为-1s更容易。
时间复杂度
这是O（N）。 主循环清楚地访问每个索引一次。 每个索引都被添加到堆栈中，并且最多只能删除一次。
作为面试问题解决
这样的问题在面试中可能相当吓人，但是我想指出的是（希望）面试官不会期望解决scheme能够完全形成。 通过你的思考过程来谈论他们。 我的是这样的：
- 数字的位置和数组中的下一个较小的数字之间是否存在某种关系？ 知道其中一些限制别人可能是什么？
- 如果我在白板前，我可能会画出示例数组，并在元素之间画线。 我也可以把它们绘制成二维条形图 – 水平轴是input数组中的位置，垂直轴是数值。
- 我有一个预感，这将显示一个模式，但没有纸手。 我认为这个图表会变得很明显。 仔细想想，我可以看到，这些线不会任意重叠，而只会嵌套。
- 围绕这一点，我想到这与Python在内部用于将缩进转换为INDENT和DEDENT虚拟令牌的algorithm非常相似，我之前已经读过这个algorithm。 请参阅“编译器如何parsing缩进？” 在这个页面上： http : //www.secnetix.de/olli/Python/block_indentation.hawk然而，直到我实际上制定了一个algorithm，我跟上这个想法，并确定它实际上是相同的，所以我不认为这太有帮助。 尽pipe如此，如果你能看到与其他一些问题的相似之处，那么提起它可能是一个好主意，并说出它是如何相似以及如何不同的。
- 从这里开始，基于栈的algorithm的总体形状就变得很明显了，但是我仍然需要考虑一下，以确保没有后续较小元素的元素可以正常工作。
即使你没有提出一个有效的algorithm，也应该让面试官看看你在想什么。 通常情况下，思维过程不仅仅是他们感兴趣的答案。对于一个棘手的问题，找不到最好的解决scheme，但是展现出问题的洞察力可能比知道一个jar头答案要好，但是却不能给出很多答案分析。
从数组结束开始制作一个BST。 对于每个值“v”，答案将是最后一个节点“右”，你插入“v”，你可以很容易地跟踪在recursion或迭代版本。
更新：
按照您的要求，您可以以线性方式来处理：
如果下一个元素小于当前元素（例如6 5 4 3 2 1），则可以线性处理，而不需要任何额外的内存。 有趣的情况是，当你开始混淆元素时（例如4 2 1 5 3），在这种情况下，只要你没有得到“较小的元素”，就需要记住它们的顺序。 一个简单的基于堆栈的方法是这样的：
将第一个元素（a [0]）推入堆栈。
对于每个下一个元素a [i]，你都可以看到堆栈，如果value（peek（））大于a [i]，那么你得到的堆栈元素的下一个更小的数字（peek（））{并且只要peek（）> a [i]}继续popup元素。 popup并打印/存储相应的值。 否则，只需将您的a [i]推回到堆栈。
在最后的堆栈中将包含那些从来没有比它们小的值的元素（在它们的右边）。 你可以在你的补充中填入-1。
例如A = [4，2，1，5，3];
stack: 4 a[i] = 2, Pop 4, Push 2 (you got result for 4) stack: 2 a[i] = 1, Pop 2, Push 1 (you got result for 2) stack: 1 a[i] = 5 stack: 1 5 a[i] = 3, Pop 5, Push 3 (you got result for 5) stack: 1 3 1,3 don't have any counterparts for them. so store -1 for them.
假设你的意思是第一个下一个元素比当前元素低，这里有两个解决scheme –
- 使用
sqrt(N)分段。 将数组分成sqrt(N)段，每段的长度为sqrt(N)。 对于每个段使用一个循环来计算它的“最小元素”。 这样，你已经预先计算了O(N)每个段的最小元素。 现在，对于每个元素，下一个下层元素可以与这个元素在同一个网段中，或者在任何后续的网段中。 因此，首先检查当前段中的所有下一个元素。 如果全部较大，则循环遍历所有后续段以找出哪个元素具有比当前元素低的元素。 如果找不到，结果会是-1。 否则，检查该段的每个元素，以找出比当前元素低的第一个元素。 总的来说，algorithm复杂度是O(N*sqrt(N))或O(N^1.5)。
您可以使用类似方法的分段树来实现O(NlgN) 。
- 先对数组进行sorting（保留元素的原始位置作为卫星数据）。 现在，假定数组中的每个元素都是不同的，那么对于每个元素，我们将需要find该元素左侧的最低原始位置。 这是一个经典的RMQ（范围最小查询）问题，可以通过多种方式解决，包括
O(N)。 由于我们需要首先sorting，总的复杂度是O(NlogN)。 您可以在TopCoder教程中了解有关RMQ的更多信息。
出于某些原因，我觉得更容易推理“先前较小的元素”，又名“最接近的较小的元素” 。 因此，向后应用给出了“下一个更小”。
为了logging，在O（n）时间，O（1）空间（即没有堆栈）的Python实现中，在数组中支持负值：
def next_smaller(l): """ Return positions of next smaller items """ res = [None] * len(l) for i in range(len(l)-2,-1,-1): j=i+1 while j is not None and (l[j] > l[i]): j = res[j] res[i] = j return res def next_smaller_elements(l): """ Return next smaller items themselves """ res = next_smaller(l) return [l[i] if i is not None else None for i in res]
这里是JavaScript代码。 这个video更好地解释了Algo
function findNextSmallerElem(source){ let length = source.length; let outPut = [...Array(length)].map(() => -1); let stack = []; for(let i = 0 ; i < length ; i++){ let stackTopVal = stack[ stack.length - 1] && stack[ stack.length - 1].val; // If stack is empty or current elem is greater than stack top if(!stack.length || source[i] > stackTopVal ){ stack.push({ val: source[i], ind: i} ); } else { // While stacktop is greater than current elem , keep popping while( source[i] < (stack[ stack.length - 1] && stack[ stack.length - 1].val) ){ outPut[stack.pop().ind] = source[i]; } stack.push({ val: source[i], ind: i} ); } } return outPut; }
输出 –
findNextSmallerElem([98,23,54,12,20,7,27]) [23, 12, 12, 7, 7, -1, -1]
这里有一个观察，我认为可以做成一个O（n log n）的解决scheme。 假设你有数组的最后k个元素的答案。 在这之前，为了弄清楚元素的价值，你需要什么？ 你可以把最后的k个元素分解成一系列的范围，每个范围从某个元素开始，继续向前，直到碰到一个更小的元素。 这些范围必须按降序排列，所以你可以考虑对它们进行二分search，find比那个元素小的第一个区间。 然后你可以更新范围来考虑这个新元素。
现在，如何最好地代表这个？ 我想到的最好的方法是使用splay树，其键是定义这些范围的元素，其值是它们开始的索引。 然后你可以在O（log n）分期的时候做一个前置search来find当前元素的前任。 这发现最早的值比当前小。 然后，在分期O（log n）时间内，将当前元素插入到树中。 这代表了从这个元素向前定义一个新的范围。 为了放弃这个取代的所有范围，您然后切割新节点的右侧子节点，因为这是一个弹性树，它位于树的根节点。
总的来说，这对O（n lg n）进行O（log n）过程的O（n）迭代。
这是一个使用DP（实际上是O（2n））的O（n）algorithm：
int n = array.length();
数组min []logging从索引ifind的最小数字，直到数组结束。
int[] min = new int[n]; min[n-1] = array[n-1]; for(int i=n-2; i>=0; i--) min[i] = Math.min(min[i+1],array[i]);
通过原始数组和min []search并比较。
int[] result = new int[n]; result[n-1] = -1; for(int i=0; i<n-1; i++) result[i] = min[i+1]<array[i]?min[i+1]:-1;
这里是find“下一个更小的元素”的新解决scheme：
int n = array.length(); int[] answer = new int[n]; answer[n-1] = -1; for(int i=0; i<n-1; i++) answer[i] = array[i+1]<array[i]?array[i+1]:-1;
All that is actually not required i think case 1: a,b answer : -a+b case 2: a,b,c answer : a-2b+c case 3: a,b,c,d answer : -a+3b-3c+d case 4 :a,b,c,d,e answer : a-4b+6c-4d+e . . . recognize the pattern in it? it is the pascal's triangle! 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 so it can be calculated using Nth row of pascal's triangle! with alternate + ans - for odd even levels! it is O(1)
具有O（1）空间复杂度和O（n）时间复杂度的解决scheme。
void replace_next_smallest(int a[], int n) { int ns = a[n - 1]; for (int i = n - 1; i >= 0; i--) { if (i == n - 1) { a[i] = -1; } else if (a[i] > ns) { int t = ns; ns = a[i]; a[i] = t; } else if (a[i] == ns) { a[i] = a[i + 1]; } else { ns = a[i]; a[i] = -1; } } }
