目录
力扣946 ---验证栈序列
题目
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true 解释：我们可以按以下顺序执行： push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false 解释：1 不能在 2 之前弹出。提示：
- 1 <= pushed.length <= 1000
- 0 <= pushed[i] <= 1000
- pushed 的所有元素 互不相同
- popped.length == pushed.length
- popped 是 pushed 的一个排列
分析
代码
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
st, j = [], 0
for x in pushed:
st.append(x)
while st and st[-1] == popped[j]:
st.pop()
j += 1
return len(st) == 0
单调栈
单调栈是一种特殊的栈结构，它在某些算法中非常有用，尤其是在处理与单调性相关的数据序列时。单调栈的特点是，它只允许栈顶元素单调递增或单调递减。根据单调性的不同，单调栈可以分为两种类型：
1. **单调递增栈**：栈中的元素必须保持单调递增的顺序，即新入栈的元素必须大于或等于栈顶元素。
2. **单调递减栈**：栈中的元素必须保持单调递减的顺序，即新入栈的元素必须小于或等于栈顶元素。
单调栈的应用场景包括但不限于：
- **Next Greater Element**：找到一个数组中每个元素右边第一个比它大的元素。
- **Next Smaller Element**：找到一个数组中每个元素右边第一个比它小的元素。
- **Longest Increasing Subsequence**（最长递增子序列）：找到给定数组中的最长递增子序列。
- **最小/最大值问题**：在数组中找到某个区间的最小或最大值。
单调栈的实现通常涉及到两个栈：一个用于存储当前的单调栈，另一个用于辅助操作。在处理数据时，可以通过比较和调整栈顶元素来维护栈的单调性。
下面是一个使用单调栈解决Next Greater Element问题的例子：
```python
def nextGreaterElements(nums):
stack = []
result = [-1] * len(nums) # 初始化结果数组为-1，表示没有更大的元素for i in range(2 * len(nums) - 1, -1, -1): # 从数组末尾开始遍历
while stack and (stack[-1] <= nums[i % len(nums)]): # 栈顶元素小于等于当前元素
stack.pop() # 弹出栈顶元素
if stack: # 如果栈不为空，说明找到了大于当前元素的元素
result[i] = stack[-1] # 将栈顶元素赋值给结果数组
stack.append(nums[i % len(nums)]) # 将当前元素压入栈return result
```
这个算法首先将数组倒序遍历一遍，然后使用一个单调递减栈来找到每个元素右边第一个比它大的元素。如果当前元素大于栈顶元素，就继续弹出栈顶元素，直到找到一个比当前元素大的元素，或者栈为空。然后将这个元素赋值给结果数组中当前索引对应的位置。如果遍历完数组，栈仍然为空，说明没有找到比当前元素大的元素，结果数组中该位置保持为-1。
力扣739 ---每日温度
题目
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]示例 2:
输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]提示：
- 1 <= temperatures.length <= 105
- 30 <= temperatures[i] <= 100
分析
代码
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
answer = [0]*len(temperatures)
for i,temp in enumerate(temperatures):
while stack and stack[-1][0]<temp:
prev_temp, prev_index = stack.pop()
# 计算当前温度和之前温度的天数差
answer[prev_index] = i - prev_index
# 将当前温度和索引压入栈中
stack.append((temp, i))
# 返回答案数组
return answer
