给定一个数组A[1..n]，我们要计算另一个数组，B[1..n]这样B[i]存储左边的最近元素A[i]小于A[i]。时间复杂度应该是O(n)。
A[1..n]
B[1..n]
B[i]
A[i]
O(n)
（对于i>1，如果左侧没有这样的较小元素，则B[i]只需包含A[i]和B[1]=A[1]。）
i>1
B[1]=A[1]
范例：
输入：6,9,12,17,11 输出：6,6，9，12，9
我想实现一个堆栈， 把A[1]中B[1]，然后推入堆栈。 用于填充B[i]，A[i]与stack和pop的元素比较，直到获得更小的元素。 最终推A[i]入堆栈。
A[1]
B[1]
以上方法正确吗，并且有更便宜的解决方案吗？
您的堆栈方法是正确的。之所以起作用，是因为如果您弹出一个大于的元素A[i]，则该元素对于以后的任何元素都将不再需要A[i]，因为您可以使用A[i]来代替。
每个元素仅被访问两次，因此是O(n)。
