给定一个数组A[1..n],我们想要计算另一个数组B[1..n],以便B[i]存储左边A[i]最小的元素小于A[i].时间复杂度应该是O(n).
(对于i>1,如果左边没有这样的小元素,那么B[i]只需包含A[i],和B[1]=A[1].)
示例:
输入:6,9,12,17,11
输出:6,6,9,12,9
我想实现一个堆栈,
把A[1]中B[1],然后推入堆栈.
填充B[i],比较A[i]堆栈和弹出元素,直到你得到更小的元素.
终于推A[i]到了堆栈.
以上方法是否正确,是否有更便宜的解决方案？