给定一个数组 A，计算 B s.t B[i] 存储离 A[i] 左边最近且小于 A[i] 的元素数组、元素、最近
给定一个数组 A[1..n]，我们想计算另一个数组 B[1..n] 使得 B[i] 存储 A[i] 左侧最近的元素，该元素小于 A[i].时间复杂度应该是O(n).
Given an array A[1..n], we want to compute another array B[1..n] such that B[i] stores the nearest element to the left of A[i] which is smaller than A[i].
Time complexity should be O(n).
(对于i>1，如果左边没有这么小的元素，那么B[i]简单地包含A[i]，并且 B[1]=A[1].)
(For i>1,If there are no such smaller elements to the left, then B[i] simply contains A[i], and B[1]=A[1].)
例子:
输入:6,9,12,17,11输出:6,6,9,12,9
input : 6,9,12,17,11 output:6,6, 9, 12, 9
我正在考虑实现一个堆栈，将 A[1] 放入 B[1]，然后压入堆栈.为了填充 B[i]，将 A[i] 与堆栈元素进行比较，然后弹出直到你得到更小的元素.最后将 A[i] 压入栈中.
I was thinking for implementing a stack,
put A[1] in B[1], then push to stack.
for filling B[i],compare A[i] with elements of stack and pop till you get smaller element.
finally push A[i] to stack.
上述方法是否正确，是否有更便宜的解决方案?
Is above approach correct, and is there a cheaper solution?
推荐答案
你的堆栈方法是正确的.它之所以有效，是因为如果你弹出一个大于 A[i] 的元素，那么 A[i] 之后的任何元素都不需要该元素，因为你可以使用 A[i] 代替.
Your stack approach is correct. It works because if you pop an element bigger than A[i], that element will never be needed for any elements following A[i], because you can just use A[i] instead.
每个元素只被访问两次，所以这是O(n).
Each element is only accessed twice, so this is O(n).
