单调栈

单调栈：栈中元素按递增或递减顺序排列

单调栈优点：时间复杂度是线性的，每个元素只遍历一次

单调栈主要回答这样的几种问题

• 比当前元素更大的下一个元素

• 比当前元素更大的前一个元素

• 比当前元素更小的下一个元素

• 比当前元素更小的前一个元素

比当前元素更小的前一个元素

image-20200705184033682

_ = input()
nums = [int(x) for x in input().split(" ")]

stk = list()
ans = [-1] * len(nums)
for i, num in enumerate(nums):
    if not stk:
        stk.append(num)
        continue
    while stk and stk[-1] >= num:
        stk.pop()
    if stk:
        ans[i] = stk[-1]
    stk.append(num)

print(ans)

比当前元素更大的下一个元素

496. 下一个更大元素 I

from typing import List


class Solution:
    # 方法1
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:

        stk, d = list(), dict()
        for num in nums2:
            # 找到右边第一个（后一个）比它大的数
            while stk and stk[-1] < num:
                d[stk.pop()] = num
            stk.append(num)
        return [d.get(num, -1) for num in nums1]

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    var stk []int
    var mp = make(map[int]int)
    for _, v := range nums2 {
        for len(stk) > 0 && v > stk[len(stk)-1] {
            mp[stk[len(stk)-1]] = v                
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, v)
    }

    for _, v := range stk {
        mp[v] = -1
    }

    var ans []int
    for _, v := range nums1 {
        ans = append(ans, mp[v])
    }
    return ans
}

503. 下一个更大元素 II

from typing import List


class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        ans = [-1] * len(nums)
        stk = list()

        nums2 = nums + nums

        for i, num in enumerate(nums2):

            # 找到第i个数的下一个比它大的元素
            while stk and nums[stk[-1]] < num:
                ans[stk.pop()] = num

            # 这里需要判断所维护的单调栈是否重复添加nums中的元素
            if i < len(nums):
                stk.append(i)

        return ans

739. 每日温度

from typing import List

"""
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。
如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
"""
"""
分析：找到下一个比当前元素a值大的元素b，b_idx - a_idx即为所求
"""


class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        ans = [0] * len(T)
        stk = list()
        for i, num in enumerate(T):
            while stk and T[stk[-1]] < num:
                # 在右边找到了第一个比"当前位置"T[stk[-1]]大的元素
                ti = stk.pop()
                ans[ti] = i - ti
            stk.append(i)
        return ans

42. 接雨水

img

from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:

        ans = 0
        stk = list()
        for i in range(len(height)):
            while stk and height[stk[-1]] < height[i]:    # 形成了凹槽
                ti = stk.pop()
                while stk and height[stk[-1]] == height[ti]: # 中间一段是“平滑的”
                    stk.pop()
                if stk:
                    ans += (i - stk[-1] - 1) * (min(height[stk[-1]], height[i]) - height[ti])

            stk.append(i)

        return ans

# 参考：https://mp.weixin.qq.com/s/f9ebzbwymR8jQeUDxjeCDA

901. 股票价格跨度

图解

class StockSpanner:

    def __init__(self):
        self.stk = list()

    def next(self, price: int) -> int:

        ans = 1
        while self.stk and self.stk[-1][0] <= price:
            ans += self.stk.pop()[-1]

        self.stk.append((price, ans))
        return ans