数据结构之单调栈

栈是很基础的一种数据结构，具有后入先出(LIFO)的特性

单调栈也是一种栈，一般用于处理具有Next Greater Element特点的问题

单调递减栈

1. 在一个队列中针对每一个元素从它右边寻找第一个比它大的元素
2. 在一个队列中针对每一个元素从它左边寻找第一个比它大的元素（从后往前遍历）

单调递增栈

1. 在一个队列中针对每一个元素从它右边寻找第一个比它小的元素
2. 在一个队列中针对每一个元素从它左边寻找第一个比它小的元素（从后往前遍历）

下一个更大元素 I

模板题

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res=defaultdict(int)
        n=len(nums2)
        stack=[]
        for i in range(n-1,-1,-1):
            while stack and stack[-1]<=nums2[i]:
                stack.pop()
            res[nums2[i]]=stack[-1] if stack else -1
            stack.append(nums2[i])
        return [res[n] for n in nums1]

下一个更大元素 II

同上，2个nums接起来做就行

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        nums=nums[:]+nums[:]
        n=len(nums)
        res=[0]*n
        stack=[]
        for i in range(n-1,-1,-1):
            while stack and stack[-1]<=nums[i]:
                stack.pop()
            res[i]=stack[-1] if stack else -1
            stack.append(nums[i])
        
        return res[:n//2]

每日温度

模板，只不过找的是下标之间的关系

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n=len(temperatures)
        stack,res=[],[0]*n
        for i in range(n-1,-1,-1):
            while stack and temperatures[stack[-1]]<=temperatures[i]:
                stack.pop()
            res[i]=stack[-1]-i if stack else 0
            stack.append(i)
        return res

链表中的下一个更大节点

链表转数组，然后模板

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        nums=[]
        while head:
            nums.append(head.val)
            head=head.next
        
        n=len(nums)
        stack=[]
        res=[0]*n
        for i in range(n-1,-1,-1):
            while stack and stack[-1]<=nums[i]:
                stack.pop()
            res[i]=stack[-1] if stack else 0
            stack.append(nums[i])
        return res

商品折扣后的最终价格

单调递增栈

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n=len(prices)
        stack=[]
        for i in range(n):
            while stack and prices[i]<=prices[stack[-1]]:
                prices[stack[-1]]-=prices[i]
                stack.pop()
            stack.append(i)
        return prices