LeetCode 补充题 186. 数组两侧最近严格较小元素的位置

约 4 分钟
文章信息 3 个分类 2 个标签
分类
补充题 中等 字节
标签
数组 单调栈

题目描述

[!green]

牛客原题： ✅ 补充题 186. 数组两侧最近严格较小元素的位置

给定允许重复值的数组。对每个下标 i，返回左侧最近的严格小于 arr[i] 的下标，以及右侧最近的严格小于 arr[i] 的下标。

不存在的一侧填 -1。

示例 1：

输入： nums = [3,1,1,2]
输出： [[-1,1],[-1,-1],[-1,-1],[2,-1]]
解释： 下标 0 右侧最近的较小值在下标 1；两个值为 1 的元素不能互相作为严格较小值；下标 3 左侧最近的较小值在下标 2。

提示：

  • 1 <= n <= 10^5
  • -10^9 <= nums[i] <= 10^9

题意分析

需要的是每一侧最近的严格较小下标。逐位置向外找会重复扫描很多元素；单调栈可保留仍可能成为后续答案的候选，将被更近且不大的元素支配的位置永久移除。

解法：两遍单调栈分别求严格更小边界

核心思路

[!blue]

从左向右扫描时，栈存下标，栈内值严格递增。当前值到来后，弹出值大于等于它的栈顶：这些位置不是当前答案；对以后的元素，当前位置更近且值不更大，也能替代它们，因此可以永久舍弃。

弹出完成后，栈顶是剩余候选中下标最近且值严格较小的位置；栈空则左侧不存在答案。记录后压入当前下标，为后续位置提供候选。

清空栈，再从右向左用相同条件求右侧答案。相等值必须弹出，才能满足“严格较小”；每个下标每遍至多入栈、出栈一次，总时间为线性。

解题步骤

  1. 正向扫描，弹出大于等于当前值的栈顶，记录左边严格更小的位置。
  2. 清空栈并逆向重复扫描，记录右边位置。
  3. 无候选时写-1，返回二元位置数组。

代码实现

class Solution {
    public int[][] nearestSmaller(int[] nums) {
        int n = nums.length;
        int size = 0;
        int[] stack = new int[n];
        int[][] result = new int[n][2];

        for (int i = 0; i < n; i++) {
            while (size > 0 && nums[stack[size - 1]] >= nums[i]) {
                size--;
            }

            result[i][0] = size == 0 ? -1 : stack[size - 1];
            stack[size++] = i;
        }

        size = 0;

        for (int i = n - 1; i >= 0; i--) {
            while (size > 0 && nums[stack[size - 1]] >= nums[i]) {
                size--;
            }

            result[i][1] = size == 0 ? -1 : stack[size - 1];
            stack[size++] = i;
        }

        return result;
    }
}

func nearestSmaller(nums []int) [][]int {
    result := make([][]int, len(nums))
    for i := range result {
        result[i] = []int{
            -1,
            -1,
        }
    }
    stack := make([]int, 0, len(nums))
    for i, x := range nums {
        for len(stack) > 0 && nums[stack[len(stack)-1]] >= x {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            result[i][0] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }
    stack = stack[:0]
    for i := len(nums) - 1; i >= 0; i-- {
        for len(stack) > 0 && nums[stack[len(stack)-1]] >= nums[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            result[i][1] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }
    return result
}

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：额外空间 $O(n)$，不计返回数组时栈仍占 $O(n)$。

关键点总结

[!green]

栈保存候选下标；当前值小于等于栈顶值时弹出，剩余栈顶才是该方向最近的严格更小值；两遍扫描让左右两侧采用相同的严格条件，避免把相等值当作答案。

易错点总结

[!yellow]

弹栈条件是大于等于；返回下标而非元素值；两遍之间必须清空栈。

相似题目

题目 难度 关联与区别
84. 柱状图中最大的矩形 困难 矩形面积可由合适的等高分工求得，本题明确要求两侧都严格更小，因此采用两次独立扫描。
739. 每日温度 中等 同样寻找最近满足大小关系的下标，原题只找右侧严格更大，本题两侧严格更小。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/62708878
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！