设计一个高效的算法，从顺序表L中删除所有值介于x和y之间的所有元素（假设y>=x），要求时间复杂度为O(n)，空间复杂度为O(1)

算法思路：

- 使用两个指针i和j，初始时i指向0位置，j指向1位置。
- 当L[j]不在x和y之间时，将L[j]复制到L[i+1]的位置，i指向i+1的位置。
- 当L[j]在x和y之间时，跳过该元素，只将j指向下一个位置。
- 最后将L[0]~L[i]的元素保留，L[i+1]~L[n-1]的元素删除。

算法实现：

def delete_between(L, x, y):
    i, j = 0, 1
    while j < len(L):
        if not (x <= L[j] <= y):
            i += 1
            L[i] = L[j]
        j += 1
    del L[i+1:]

算法分析：

- 时间复杂度为O(n)，因为只需要遍历一次顺序表L。
- 空间复杂度为O(1)，因为只需要使用两个指针i和j，没有额外的空间开销。

相关问题

2．设计已知一个顺序存储的线性表的元素非递减有序排列。编写删除表中介于x-y之间的所有元素的高效算法。

为了设计一个删除线性表中元素非递减有序排列的算法，我们可以采用双指针策略。假设我们有一个数组`arr[]`表示顺序存储的线性表，并且`arr[0]`到`arr[y]`是已排序部分，`arr[x+1]`到`arr[n-1]`是非递减有序的部分。

以下是算法步骤：

1. 初始化两个指针，`i = x` 和 `j = y + 1`。这两个指针分别指向要删除区间的开始和结束。

2. 当 `j < n` 时，进入循环：
a. 检查 `arr[j]` 是否大于等于 `arr[i]`（因为我们要删除的是非递增序列）。如果是，则说明我们需要将 `arr[j]` 移动到已删除区间的前面，即 `arr[i] = arr[j]`。
b. 将 `j` 向右移动一位，继续检查下一个元素。
c. 如果 `arr[j]` 小于 `arr[i]`，说明找到了一个合适的插入位置，直接结束当前循环，并跳过剩余的已删除区间（`i++`）。

3. 循环结束后，`i` 的位置将是新序列的结尾。所有小于等于 `arr[i]` 的元素都被删除了。

4. 更新线性表的长度为 `n - (j - i)`，并把 `arr` 中从索引 `i` 到 `n-1` 的元素视为新的非递减有序序列。

**伪代码如下：**

def removeElements(arr, x, y):
    i = x
    j = y + 1
    
    while j < len(arr):
        if arr[j] >= arr[i]:
            # Move non-decreasing element to the front
            arr[i] = arr[j]
            i += 1
        else:
            break
        j += 1

    # Update the length and shift elements after i
    arr = arr[:i]
    return arr