咨询：移除最少元素实现非重排数组的降序排列方案

嘿，咱先把问题的本质掰扯清楚——你的需求其实核心就是找原数组的最长递减子序列（LDS），但看你说LDS不适用，大概率是对这个算法的应用场景有误解，或者你的场景有额外的隐藏约束？下面我分情况给你拆解，应该能解决你的问题：

先理清楚基础情况：只移除元素的场景 #

如果只是允许移除元素，最终数组是原数组的一个子序列（元素顺序完全和原数组一致）且满足降序，同时要保留最多元素（也就是移除最少），那标准的LDS算法绝对是最优解。举个例子，原数组是[5, 2, 6, 3, 1]，最长递减子序列要么是[5,3,1]要么是[6,3,1]，留着这些元素删掉其他，就是你要的结果。

那你说LDS不适用，估计是遇到了下面这些特殊场景，咱一个个说解决方案：

特殊场景的应对方案 #

场景1：需要保持原数组长度，用null填空缺 #

如果要求最终数组和原数组长度一模一样，只是把不需要的位置设为null，那步骤很简单：

1. 用LDS算法找到最长递减子序列的元素位置索引（别只找值，要记下来在原数组里的位置）
2. 新建一个和原数组长度相同的数组，先全设为null
3. 把LDS索引对应的原数组值，复制到新数组的对应位置
4. 搞定！最终的数组里，非null元素严格按原顺序降序，而且数量是最多的，也就是填充null的数量最少。

举个实际例子：
原数组：[5, 3, 4, 2]
我们选的LDS索引是[0,2,3]（对应值[5,4,2]）
新数组就是：[5, null, 4, 2]，完全符合你的要求。

场景2：数组里有大量重复元素，需要支持非严格降序 #

如果你的“降序”允许相等元素（比如5,5,3这种也算合法），那只需要把LDS算法里的比较条件改一改就行：

• 原本严格降序是“当前元素小于栈顶元素才入栈”，改成“当前元素小于等于栈顶元素就入栈”
• 替换逻辑也跟着调整，这样就能得到最长的非严格递减子序列了。

场景3：有多个LDS解，需要优先保留靠前/靠后的元素 #

有时候同一个数组可能有好几个长度相同的最长递减子序列，如果你想优先保留原数组里更靠前的元素，或者更靠后的，那在LDS算法的回溯阶段调整选择策略就行：

• 要靠前的：遇到相同值的元素时，选索引更小的那个
• 要靠后的：遇到相同值的元素时，选索引更大的那个

针对大型数组的优化（数千条记录完全没问题） #

你的数组有数千条记录，完全不用担心性能——O(n log n)复杂度的LDS算法处理1万条数据都快得很，步骤大概是这样（以严格降序为例）：

1. 搞个空栈stack，用来存LDS的候选值
2. 再搞个prev_indices数组，记录每个元素在LDS里的前一个元素索引，方便后面回溯找具体位置
3. 遍历原数组的每个元素num和它的索引i：
   • 如果num比栈顶元素小，直接把num压栈，同时记下来prev_indices[i]是栈倒数第二个元素的索引
   • 如果num不小于栈顶元素，就找栈里第一个比num小的元素，把它替换成num，同时更新对应的prev_indices
4. 遍历完后，通过prev_indices回溯，就能拿到最长递减子序列的所有索引
5. 最后根据这些索引构建你要的数组（要么移除其他元素，要么填null）

为啥你觉得LDS不适用？ #

如果上面的场景都不对，那可能是你对“不可重新排序”的理解有点偏差？比如是不是要求相邻的非null元素必须降序？但根据你说的“剩余未移除元素构成降序数组”，只要这些元素按原顺序是降序就行，不管中间有没有null或者被移除的元素，那LDS肯定是最优解。

要是还有啥特殊约束没说出来，可以补充，但目前按你的描述，LDS及其扩展方案就是最直接的解决办法。

内容的提问来源于stack exchange，提问作者Ashfaq Salehin