请选择 进入手机版 | 继续访问电脑版
点击联系客服
客服QQ:509006671 客服微信:mengfeiseo

兰州老站长

 找回密码
 立即注册
查看: 69|回复: 0

需要面试刷题:单调的堆栈python模板例程(与使用案例一起详细说明)

[复制链接]

1

主题

1

帖子

-7

积分

限制会员

积分
-7
发表于 2021-3-7 14:33:01 | 显示全部楼层 |阅读模式
单调栈问题:

要想知道单调的堆栈适合解决什么问题,首先要知道单调的堆栈的作用。单调堆栈分为单调增量堆栈和单调减少堆栈,使用单调堆栈可以访问下一个较大(较小)的元素(或示例)。

也就是说,当需要比较队列或数组中前后元素的大小关系来解决问题时,通常使用单调的堆栈。下面简要介绍单调堆栈和单调堆栈问题,详细说明使用单调堆栈处理问题的过程。

什么时候使用单调栈?

通常是一维阵列,在所有元素的右侧(左侧)找到比自己大的(小)第一个元素,并要求O(n)的时间复杂性

单调栈原理:

单调增量堆栈:从堆栈底部增加到堆栈顶部,堆栈顶部较大

单调递减堆栈:从堆栈底部减少到堆栈顶部,堆栈顶部较小

python模板套路:

1):当前项目向右找到第一个比自己大的位置3354,从右到左保持单调的减少堆栈。

def  nextgreaterelement  _ 01(nums  3360列表)3360

长度=len  (nums)

Res,stack=[-1] *长度,[]

For  I  inrange(长度-1,
pan> -1, -1):
        while stack and stack[-1]  nums:
            stack.pop()
        if stack:
            res = stack[-1]
        stack.append(nums)
    return res

或者 当前项向右找第一个比自己大的位置 —— 从左向右维护一个单调递减栈。

def nextGreaterElement_011(nums: list):
    length = len(nums)
    res, stack = [-1] * length, []
    for i in range(length):
        while stack and nums[stack[-1]]  nums:
            idx = stack.pop()
            res[idx] = nums
        stack.append(i)
    return res

2):当前项向右找第一个比自己小的位置 —— 从右向左维护一个单调递增栈

def nextGreaterElement_02(nums: list):
    length = len(nums)
    res, stack = [-1] * length, []
    for i in range(length - 1, -1, -1):
        while stack and stack[-1] >= nums:
            stack.pop()
        if stack:
            res = stack[-1]
        stack.append(nums)
    return res

3): 当前项向左找第一个比自己大的位置 —— 从左向右维护一个单调递减栈

def nextGreaterElement_03(nums: list):
    length = len(nums)
    res, stack = [-1] * length, []
    for i in range(length):
        while stack and stack[-1]  nums:
            stack.pop()
        if stack:
            res = stack[-1]
        stack.append(nums)
    return res

4): 当前项向左找第一个比自己小的位置 —— 从左向右维护一个单调递增栈

def nextGreaterElement_04(nums: list):
    length = len(nums)
    res, stack = [-1] * length, []
    for i in range(length):
        while stack and stack[-1] >= nums:
            stack.pop()
        if stack:
            res = stack[-1]
        stack.append(nums)
    return res


参考来源:https://leetcode-cn.com/problems/next-greater-element-i/solution/dan-diao-zhan-zong-jie-by-wu-xian-sen-2/

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|无图版|手机版|小黑屋|兰州@IT精英团

GMT+8, 2021-4-14 18:09 , Processed in 0.083228 second(s), 25 queries .

Powered by Discuz! X3.4

Copyright © 2021, Tencent Cloud.

快速回复 返回顶部 返回列表