在数组中删除小于左侧元素的元素。

Question

我正在尝试编写一个程序，其输入是一个整数数组和它的大小。这个代码必须删除比左侧元素小的元素。我们想要找出重复此操作的次数，以便不能再删除任何元素。以下是我的代码，它可以工作，但我希望它更快。

你有什么办法可以让这段代码更快，或者有一种更快的方法吗？

例如，给定数组[10,9,7,8,6,5,3,4,2,1]，该函数应返回2，因为[10,9,7,8,6,5,3,4,2,1] → [10,8,4] → [10]。

int numberOfTimes(int array[] , int n) {
    int count = 0;
    int flag = 0;
    int sizeCounter = 0;
    while (true){
        for (int i = 0; i < n-1; ++i) {
            if (array[i]<= array[i+1]){
                sizeCounter++;
                array[sizeCounter] = array[i+1];
            } else{
                flag = 1;
            }
        }
        if (flag == 0)
            return count;

        count++;
        flag = 0;
        n = (sizeCounter+1);
        sizeCounter = 0;
    }
}

- asd

---

@Stef，你能解释一下如何通过在内存中保留已见最大元素来一次性完成的方法吗？ - asd

我没有完整的解决方案，但我会开始通过识别峰值、谷底、下降斜率和上升斜率来解决这个问题。例如，在数组 [10,5,3,4,6,8,7,1] 中，峰值是 10 和 8，谷底是 3 和 1，下降斜率是 10,5,3 和 8,7,1，上升斜率是 3,4,6,8。下降斜率在单次遍历中被移除。每次遍历将删除一个元素的上升斜率。因此，这个例子有 4 个计数，因为最长的上升斜率有四个元素，而峰值 8 小于峰值 10。 - user3386109

@wLui155 但是这个问题并不等同。考虑这个例子：array=[10,8,7,6,9] → [10,9] → [10]。答案是2。然而对于 i=4，我们得到 j=0，且 i-j = 4. - Stef

@Stef 很好的发现。我的“距离”定义在这种情况下并不完全正确；它应该与删除一个元素所需的轮数同义。事实证明，正确的“距离”定义是递归的，这使得事情有点棘手：对于每个 j < i，如果 array[j] < array[i]，则 distance[i] = max(distance[j]) + 1。如果不存在这样的 j，则 distance[i] = 0。幸运的是，这个问题也可以在线性时间内解决，这符合10^5约束的大小。 - wLui155

我基本上声称删除array[i]所需的轮数为1.0（未删除array[i]）2.1（其相邻元素array[i-1]>array[i]）或3.查找左侧最接近array[i]的较大元素array[k]。然后，删除的次数是在索引k和i之间删除某些中间元素所需的最大轮数加一。如描述的那样，该问题似乎需要O（N ^ 2）时间才能解决，但通过一些巧妙的操作，可以更快地完成。 - wLui155

Answer 1

使用“单调栈”算法，可以在O(n)时间和O(n)空间内解决此问题。

对于数组的每个元素，我们将找到删除该元素所需的“动作/轮次”数量。换句话说，必须经过多少轮才能删除当前元素（包括当前元素）和左侧最近的较大元素之间的所有元素。

如果我们知道该数字（称为“轮次”），则可以找到所有数组元素中该值的最大值，并知道删除可删除的所有元素所需的轮次。这就是我们的答案。

现在，如何找到“轮次”值？如果我们已经为当前元素左侧的所有元素计算出了这些“轮次”值，那么很容易。我们只需找到最接近当前元素的大于当前元素的元素，并找到该元素和当前元素之间的每个元素的最大“轮次”数。即如果当前元素位于索引i处，并且最接近的大于当前元素的元素位于索引j处（jarray[i]），则turns[i] = max(turns[k]+1)，其中k在[j+1..i-1]范围内。

如果我们采用朴素方法为每个元素查找“轮次”，则需要O(n)时间。幸运的是，我们很容易看出，当我们为某些i找到了j时，我们将永远不需要再考虑j和i之间的元素。请记住，array[j]>array[i]，并且j和i之间的所有元素都小于array[i]。我们正在寻找最接近某个值的数组元素，因此，如果array[i]不是答案，则整个[j+1..i-1]范围也不是答案，我们可以直接转向j。

有了这一点，我们就来到了单调栈。我们只为我们已经访问过的“array”的严格递减子序列存储其每个元素的“轮次”，而不是存储“array”的每个元素的“轮次”。

在将新元素添加到栈之前，首先需要删除每个小于当前元素的元素。然后，堆栈的顶部将是我们的array[j]。

由于每个元素只会被添加到栈中一次并被移除一次，因此找到每个元素的“turns”的摊销成本为O(1)，所以整个算法的时间复杂度为O(n)。在最坏的情况下，栈的大小将增长到与数组相同的大小（如果数组严格递减）。因此，空间复杂度为O(n)。

以下是代码（Python）：

array = [10, 9, 7, 8, 6, 5, 3, 4, 2, 1]
s = [] # monotonic stack of pairs (array[j],turns[j])
count = 0 # result: number of turns to delete all deletable elements

for el in array:
  # initially assuming current element can be deleted
  turns = 1 
  
  # peeking at the top of the stack
  while len(s) > 0 and s[-1][0] <= el:
    _,t = s.pop()
    turns = max(t+1, turns)

  # corner case: current element is the largest so far, cant be deleted
  if len(s) == 0:
    turns = 0
  s.append( (el, turns) )
  count = max(count, turns)

print(count)

测试：

[10, 9, 7, 8, 6, 5, 3, 4, 2, 1] → 2
[10, 9, 7, 8, 6, 5, 3, 4, 2, 1, 9] → 3
[10, 9, 7, 8, 6, 5, 3, 4, 2, 1, 11] → 2
[] → 0
[1, 2, 3] → 0
[1, 2, 3, 1] → 1
[10, 1, 2, 3, 4, 5] → 5

---

更新：我刚刚读了评论，想向 @wLui155 致敬，他在我之前就提出了同样的核心思想。

- Aivean