给定一个长度为n的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1
时间: 2025-06-29 17:04:03 浏览: 7
### 解决方案
为了找到数组中每个元素左侧的第一个更小的元素,可以采用栈结构来实现这一目标。对于每一个当前处理的元素,在栈内保存的是尚未找到其右侧更大或相匹配元素的位置索引。当遍历到一个新的元素时,如果该元素小于栈顶位置所对应的值,则说明找到了这些位置对应元素所需的左侧第一个较小值。
具体来说:
- 初始化一个空的结果列表 `result` 和一个用于存储下标的单调递减栈 `stack`.
- 遍历输入数组中的每一个元素及其索引。
- 对于每个元素,检查并弹出所有栈中大于等于当前元素的项直到遇到一个小于它的数或者栈为空为止;在此过程中被移除的任何项目都意味着已经为其找到了右边最近的小于自身的数值。
- 如果此时栈不为空,则栈顶即为所需记录的答案之一(因为按照上述逻辑,只有比它大的才会继续留在栈里),否则表示不存在这样的前驱节点,默认返回 -1 或者其他指定标记。
- 将当前位置压入栈等待后续比较[^4].
下面是具体的 Python 实现方式:
```python
def prevSmaller(nums):
result = [-1] * len(nums) # Initialize output with default value (-1).
stack = [] # Stack will store indices.
for i, num in enumerate(nums):
while stack and nums[stack[-1]] >= num:
stack.pop() # Remove elements not less than current one.
if stack: # If there's still something on the stack,
result[i] = nums[stack[-1]] # It must be smaller and closer from left side
stack.append(i) # Push this position onto our "waiting" list
return result # Return final results after processing all numbers.
```
此方法的时间复杂度主要取决于一次完整的线性扫描以及每次操作最多涉及的一次完整清理过程,因此整体上保持在线性级别 O(n),其中 n 是给定序列长度。空间消耗同样接近 O(n), 主要是因为可能需要额外的空间去维护整个数据集大小级别的辅助栈。
阅读全文
相关推荐



















