寻找无序数组每个元素右侧最大较小元素——求栈类更优解法

给定无序数组（如arr = [5, 6, 7, 8, 4, 5, 6]），为每个索引i找到满足以下条件的arr[j]（若无符合条件的元素则返回-1）：

• j > i
• arr[j] < arr[i]
• arr[j]是[i+1, 数组末尾]中所有小于arr[i]的元素里最大的
• 若存在多个符合条件的j，取最小的那个

输入示例：[5, 6, 7, 8, 4, 5, 6]
输出示例：[4, 5, 6, 6, -1, -1, -1]

• 暴力法：通过两层循环遍历实现，时间复杂度O(N²)，数据量较大时效率极低。
• 平衡BST法：时间复杂度O(NlogN)，但需要实现AVL或红黑树结构，还要处理中序前驱查找逻辑，代码复杂度高，维护成本大。

我们可以利用单调栈实现时间复杂度O(N)、空间复杂度O(N)的解法，核心思路是从右往左遍历数组，维护一个单调递增的栈来保存候选元素的（值、索引）信息，同时处理相同值元素以保证取到最小的j。

具体步骤 #

1. 从数组末尾开始向左遍历每个元素arr[i]。
2. 弹出栈顶所有大于等于arr[i]的元素——这些元素无法成为当前或左侧元素的有效候选。
3. 此时栈顶元素即为满足条件的最大小于arr[i]的元素：
   • 栈不为空时，栈顶元素的值就是对应结果；
   • 栈为空时，结果为-1。
4. 将当前元素(arr[i], i)压入栈前，先弹出栈中所有相同值的元素——保留当前索引（更靠左的索引），确保后续元素遇到相同候选值时能取到最小的j。

代码实现（JavaScript） #

function findNextLargestSmaller(arr) {
    const n = arr.length;
    const result = new Array(n).fill(-1);
    const stack = []; // 存储格式: [值, 索引]，保持栈内元素单调递增

    for (let i = n - 1; i >= 0; i--) {
        // 移除所有不满足"小于当前元素"的候选
        while (stack.length > 0 && stack[stack.length - 1][0] >= arr[i]) {
            stack.pop();
        }
        // 记录结果
        if (stack.length > 0) {
            result[i] = stack[stack.length - 1][0];
        }
        // 移除相同值的元素，保留当前更靠左的索引
        while (stack.length > 0 && stack[stack.length - 1][0] === arr[i]) {
            stack.pop();
        }
        stack.push([arr[i], i]);
    }

    return result;
}

// 测试示例
const arr = [5, 6, 7, 8, 4, 5, 6];
console.log(findNextLargestSmaller(arr)); // 输出: [4, 5, 6, 6, -1, -1, -1]

解法说明 #

• 时间复杂度：每个元素最多入栈和出栈各一次，整体为O(N)。
• 空间复杂度：栈的最大长度不超过数组长度，为O(N)。
• 逻辑合理性：
  • 单调递增栈保证了栈顶元素是当前元素右侧最大的小于它的值；
  • 弹出相同值元素并保留当前索引，确保后续元素遇到相同候选值时，能取到最小的j（从右往左遍历，当前索引i比栈中已有的相同值元素索引更小）。

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