算法学习之单调栈详解

创作时间:

作者:

@小白创作中心

算法学习之单调栈详解

引用

CSDN

https://m.blog.csdn.net/black_cat7/article/details/143107402

单调栈的基本概念和作用

什么是单调栈？

单调栈是指栈内元素保持单调递增或单调递减顺序的一种栈结构。这种特性使得单调栈在解决某些特定类型的问题时表现出色，如寻找下一个更大或更小的元素、区间查询等。

单调栈的作用

单调栈主要用于解决以下几类问题：

寻找数组中每个元素的下一个更大或更小的值。
在一个序列中快速定位满足特定条件的最长或最短子序列。
处理区间最大最小值问题。

示例代码

示例一：寻找下一个更大的元素

给定两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对于 nums1 中的每一个数，在 nums2 中找到这个数右边的第一个比它大的数。如果不存在，则输出 -1。

def nextGreaterElement(nums1, nums2):
    stack = []  # 用于存放遍历过的元素
    map = {}  # 存放结果的映射
    
    for num in nums2:
        while stack and stack[-1] < num:
            map[stack.pop()] = num
        stack.append(num)
    
    return [map.get(n, -1) for n in nums1]

示例二：直方图中最大的矩形面积

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨后能接多少雨水。

def largestRectangleArea(heights):
    heights.append(0)  # 添加哨兵
    stack = [-1]  # 初始化栈，哨兵
    result = 0
    
    for i, h in enumerate(heights):
        while heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            result = max(result, height * width)
        stack.append(i)
    
    return result

示例三：寻找左边第一个小于当前元素的位置

给定一个整数数组，返回一个新的数组，新数组中的每个元素为原数组中该元素左边第一个小于它的元素的位置，如果没有则为 -1。

def leftSmaller(nums):
    stack = []
    result = [-1] * len(nums)
    
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] >= num:
            stack.pop()
        if stack:
            result[i] = stack[-1]
        stack.append(i)
    
    return result

示例四：寻找右边第一个大于当前元素的位置

与寻找左边第一个小于当前元素的位置类似，这里的目标是找到每个元素右边第一个大于它的元素的位置。

def rightLarger(nums):
    stack = []
    result = [len(nums)] * len(nums)  # 默认值设为数组长度，表示不存在
    
    for i in reversed(range(len(nums))):
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()
        if stack:
            result[i] = stack[-1]
        stack.append(i)
    
    return result

示例五：股票的最佳买卖时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来找出你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。但是，你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

def maxProfit(prices):
    stack = []
    profit = 0
    
    for price in prices:
        while stack and stack[-1] > price:
            profit += stack[-1] - stack.pop(0)
        stack.append(price)
    
    while stack:
        profit += stack[-1] - stack.pop(0)
    
    return profit