如何找出数组中每个元素左侧的全局最大值（非左侧首个更大元素）

安全阿岳

2026-8-6

问题解决：获取数组每个元素左侧的全局最大值

原代码分析

你的现有代码使用单调栈实现了左侧首个更大元素的查找逻辑，但要获取左侧全局最大值（即当前元素左边所有元素中的最大值），逻辑需要调整——全局最大值不需要关注“首个”，只需要维护遍历过程中遇到的最大值即可。

修改后的实现

方法1：直接维护全局最大值（最优解，时间复杂度O(n)）

不需要栈结构，仅在遍历过程中记录当前最大值，每一步直接用该值作为当前元素的左侧全局最大值：

public static void main(String[] args) {
    int a[] = {3, 0, 0, 2, 0, 4};
    ArrayList<Integer> al = new ArrayList<>();
    // 第一个元素左侧无元素，用-1表示，可根据需求调整
    int leftGlobalMax = -1;
    for (int i = 0; i < a.length; i++) {
        al.add(leftGlobalMax);
        // 更新全局最大值：当前元素更大则替换
        if (a[i] > leftGlobalMax) {
            leftGlobalMax = a[i];
        }
    }
    System.out.println(al);
}

输出结果：[-1, 3, 3, 3, 3, 3]，对应每个元素左侧的全局最大值。

方法2：基于原单调栈逻辑修改

如果坚持用栈实现，可调整栈的维护逻辑，让栈中始终保存当前全局最大值的索引：

public static void main(String[] args) {
    int a[] = {3, 0, 0, 2, 0, 4};
    Stack<Integer> st = new Stack<>();
    ArrayList<Integer> al = new ArrayList<>();
    for (int i = 0; i < a.length; i++) {
        if (st.empty()) {
            al.add(-1);
        } else {
            al.add(a[st.peek()]);
        }
        // 当前元素更大时，清空栈并更新为当前元素的索引
        if (st.empty() || a[i] > a[st.peek()]) {
            st.clear();
            st.push(i);
        }
    }
    System.out.println(al);
}

输出结果与方法1一致，但该方法效率低于直接维护最大值的方案。