给定一个数组A，计算乙ST B〔I]卖场最近的元素的[I]左边是小于A [I] [英] Given an array A,compute B s.t B[i] stores the nearest element to the left of A[i] which is smaller than A[i]

问题描述

由于数组 A [1..1] ，我们要计算另一个数组 B [1..1] 等>的存储最近的元素 A [1] 这是小左比 A [1] 。 时间复杂度应 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＆GT; 1 ，如果有向左没有这样的较小的元素，那么 B [I] 只包含 A [1] 和 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 [1] 与堆栈元素和流行，直到你得到更小的元素。
终于推 A [1] 堆栈。

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 [1] 元素更大，该元素将永远不会被需要以下 A的任何元素[I] ，因为你可以使用 A [1] 代替。

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).

这篇关于给定一个数组A，计算乙ST B〔I]卖场最近的元素的[I]左边是小于A [I]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！