将数组零移至末尾且非零元素替换为最近更大值的优化方案求解

需求说明 #

给定未排序数组，需要完成两个逻辑：

• 所有零值移动到数组末尾，保持非零元素的原始相对顺序
• 每个非零元素替换为它之后出现的最近更大值，如果后续没有更大值则保留原值

输入示例：{6,1,5,0,0,3,8,6,4}
输出示例：{8,3,6,4,8,6,4,0,0}

原实现存在的问题 #

你当前的代码采用双重循环遍历，最坏时间复杂度为O(n²)，当数组长度较大时性能损耗严重，且栈的使用逻辑冗余，没有发挥单调栈的线性时间优势。

优化实现方案 #

我们采用标准单调栈求解下一个更大元素，整体时间复杂度降到O(n)，空间复杂度O(n)，实现逻辑如下：

import java.util.Stack;

public class NextClosestBiggerElement {
    public static void main(String[] args) {
        int[] input = {6, 1, 5, 0, 0, 3, 8, 6, 4};
        int n = input.length;
        
        // 第一步：提取非零元素，统计零的个数
        int zeroCount = 0;
        int[] nonZero = new int[n];
        int m = 0;
        for (int num : input) {
            if (num != 0) {
                nonZero[m++] = num;
            } else {
                zeroCount++;
            }
        }
        
        // 第二步：单调栈从后往前求每个非零元素的下一个最近更大值
        int[] res = new int[m];
        Stack<Integer> stack = new Stack<>();
        for (int i = m - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nonZero[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? nonZero[i] : stack.peek();
            stack.push(nonZero[i]);
        }
        
        // 第三步：拼接结果，后面补零
        int[] output = new int[n];
        System.arraycopy(res, 0, output, 0, m);
        for (int i = m; i < n; i++) {
            output[i] = 0;
        }
        
        // 输出结果
        for (int num : output) {
            System.out.println(num);
        }
    }
}

优化点说明 #

• 避免了双重循环，整体时间复杂度从O(n²)降到O(n)，数组越长性能提升越明显
• 逻辑拆分清晰，先处理零和非零元素分离，再用单调栈批量处理下一个更大值，后续维护成本更低
• 栈操作每个元素最多入栈和出栈各一次，没有冗余计算

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