如何在删除/添加/更新元素后连续检查数组是否已排序

Question

假设给出一个包含 n 个整数的列表（该列表不需要已经排序）。如何检查删除、更新或插入值后列表是否已排序（非递增或非递减）？

我能想到解决这个问题的唯一方法是通过删除[O(n)]、插入[O(n)]和更新[O(n)]操作来保留数字的链表以及线性检查查看其排序是非递减还是非递增。有可能更快地解决这个问题吗？

删除、插入和更新意味着用户将给出一个要删除/插入/更新的位置，并且将在给定位置上插入、删除或添加值。

随时都会对输入进行查询，询问列表处于哪种状态（非递增或非递减）

Answer 1

这是非递减的逻辑（将其复制并扭曲为非递增）。

跟踪相邻对的数量，x, y使得x > y，即减少对。当且仅当该数字为零时，该列表才是非递减的。

要在和( )b之间插入：aca, c => a, b, c

num_decreasing_pairs -= a > c
num_decreasing_pairs += a > b
num_decreasing_pairs += b > c

要删除和( )b之间的内容：aca, b, c => a, c

num_decreasing_pairs -= a > b
num_decreasing_pairs -= b > c
num_decreasing_pairs += a > c

要更新b1到和( )b2之间：aca, b1, c => a, b2, c

num_decreasing_pairs -= a > b1
num_decreasing_pairs -= b1 > c
num_decreasing_pairs += a > b2
num_decreasing_pairs += b2 > c

所有这些语句都应该受到 ifs 的保护，检查检查的元素是否存在（边缘情况）。