leetcode-Stack

栈

用栈表示队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []
        
    def empty(self)-> bool:
        # 当in和out全空时，为空，两种都可
        return not(self.stack_in or self.stack_out)
    	return not self.stack_in and not self.stack_out
     
    def push(self, num:int)-> None:
        # 只倒入到in中
        self.stack_in.append(num)
    
    def pop(self, num:int)-> int:
        # 先从in中倒到out中，再从out中倒出来
        if self.empty():
            return None
       	if self.stack_out:
            return self.stack_out.pop()
        else:
            while self.stack_in():
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()
        
    def peek(self)-> int:
        ans = self.pop()
        self.stack_out.append(ans)
        return ans

单调栈

  1. 单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小

    当前元素后面第一个比他大的元素

  2. 单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大

    当前元素后面第一个比他小的元素

栈中可以存储当前元素的index和或者value，或者将两个值以元组的形式存储起来(index, value)

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。

更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。

一般的处理流程:

当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况

当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况

当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
for num in nums: #遍历当前的数据
    if stack is None  or stack[0] >= target:# 如果栈为空或者栈顶元素大于等于当前的比较元素
        stack.append(num) # 入栈，主要是用来更新stack
    else:
        while stack is not None and stack[0] < target: # 当栈不为空并且栈顶元素小于当前比较元素
            stack.pop() # 栈顶元素出栈
            pass # 更新结果
  
        stack.append(num)# 当前数据入栈

def dailyTemperatures(temperatures:List[int]) -> List[int]:
    n = len(temperatures)
    res = [0] * n
    stack = [0]
    for i in range(1, n):
        if temperatures[i] < temperatures[stack[-1]]: # 更新stack
            stack.append(i)
        elif temperatures[i] == temperatures[stack[-1]]: # 更新stack
            stack.append(i)
        else:
            while stack and temperatures[i] > temperatures[stack[-1]]:
                # while 持续循环弹出栈顶元素，并使用res记录结果
                res[stack[-1]] = i -  stack[-1]
                stack.pop()
			stack.append(i)
	return res