2. 算法-(单调)栈

四道经典例题带你搞定单调栈 1475、739、496、

注意单调栈中有时候存放的是数字本身，有时候存放数字的索引，根据题目灵活选择

1475. 商品折扣后的最终价格

存放下标

def finalPrices(self, prices: List[int]) -> List[int]:
        stack = []
        i = 0 
        n = len(prices)
        while i < n:
            while stack and prices[i]<=prices[stack[-1]]:
                prices[stack[-1]]-=prices[i]
                stack.pop()
            stack.append(i)
            i+=1
        return prices

739. 每日温度

存放下标, 注意对于温度列表中的每个下标，最多有一次进栈和出栈的操作 所以最终时间复杂度还是 O(N)

def dailyTemperatures(self, T: List[int]) -> List[int]:
        l = len(T)
        stack = []
        res = [0] * l
        i = 0 
        while i < l:
            while stack and T[stack[-1]]<T[i]:
                res[stack[-1]]=i-stack[-1]
                stack.pop()
            stack.append(i)
            i += 1
        return res

496. 下一个更大元素 I

def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        dic = {x:-1 for x in nums2}
        i = 0
        while i < len(nums2):
            while stack and nums2[i]>stack[-1]:
                dic[stack[-1]]=nums2[i]
                stack.pop()
            stack.append(nums2[i])
            i += 1
        return [dic[x] for x in nums1]

84. 柱状图中最大的矩形

有点难，需要继续深入研究下怎么用单调栈

3. 剑指 Offer 30. 包含min函数的栈

用去双栈模拟最小栈，一个栈用来存储，一个栈用来保持最小值，还是很经典的

class MinStack:
    def __init__(self):
        self.A, self.B = [],[]
    def push(self, x: int) -> None:
        self.A.append(x)
        if(not self.B or x<self.B[-1]):
            self.B.append(x)  
    def pop(self) -> None:
        if(self.A.pop()==self.B[-1]):
            self.B.pop()
    def top(self) -> int:
        return self.A[-1]
    def min(self) -> int:
        return self.B[-1]

6. 面试题 03.04. 化栈为队

搞定了，吼吼吼

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.A,self.B = [],[]


    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.A.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if(not self.B):
            while(self.A):
                self.B.append(self.A.pop())
        return self.B.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if(not self.B):
            while(self.A):
                self.B.append(self.A.pop())
        return self.B[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return False if self.B or self.A else True

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

如何用两个数组（栈）实现队列！！！有意思