arrays - 删除小于数组左侧元素的元素

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;
    }
}

Answer 1

这个问题可以使用“单调堆栈”在 O(n) 时间和 O(n) 空间内解决。

对于 array 的每个元素我们将找到删除元素所需的“ Action /回合”数。换句话说，必须经过多少圈，才能删除当前元素(含)和左边最近的较大元素之间的所有元素。

如果我们知道这个数字(我们称它为 turns )，那么我们就可以为我们的数组的所有元素找到这个值的最大值，并且我们将知道从数组中删除所有元素所需的轮数被删除。我们会有答案。

现在，我们如何找到 turns值(value)？这很容易，如果我们有这些 turns为当前元素左侧的所有元素计算的值。我们只是找到最近的大于当前元素的元素，并找到 turns 的最大数量。对于该元素和当前元素之间的每个元素。 IE。如果当前元素位于索引 i ，并且最近的更大元素位于索引 j 处( j < i 和 array[j] > array[i] )，turns[i] = max(turns[k]+1), for k in [j+1..i-1] .

如果我们天真地这样做，找到 turns对于每个元素都是 O(n)。幸运的是，很容易看出，当我们找到 j 时对于一些 i , 我们永远不需要考虑 j 之间的元素和 i以后再。记住，array[j] > array[i]以及介于 j 之间的所有内容和 i小于 array[i] .我们正在寻找大于某个值的最接近的数组元素，因此，如果 array[i]不是答案，整个[j+1..i-1]范围也不是答案，我们可以直接转到j .

考虑到这一点，我们到达了单调堆栈。而不是存储 turns对于 array 的每个元素, 我们只为 array 的严格递减子序列存储它到目前为止我们已经访问过。

在向堆栈中添加新元素之前，首先我们需要移除所有小于当前元素的元素。然后堆栈的顶部将是我们的 array[j] .

由于每个元素都被添加到堆栈并恰好被删除一次，所以找到 turns 的摊销成本对于每个元素是 O(1)，所以整个算法是 O(n)。在最坏的情况下，堆栈的大小会增长到与数组相同的大小(如果 array 严格递减)。所以空间复杂度为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

---

UPD:我刚刚阅读了评论，我想感谢@wLui155，他在我之前提出了相同的核心想法。