在处理数组和链表相关问题时，双指针技巧是经常用到的，
双指针技巧主要分为两类：左右指针和快慢指针。
例如：2sum
滑动窗口
一种特殊的双指针方法。
滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组。
- 初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头
重点：
1、什么时候应该扩大窗口？
2、什么时候应该缩小窗口？
3、什么时候应该更新答案？
# 滑动窗口算法框架
def slidingWindow(s: str):
# 用合适的数据结构记录窗口中的数据，根据具体场景变通
# 比如说，我想记录窗口中元素出现的次数，就用 map
# 我想记录窗口中的元素和，就用 int
window = dict()
left = 0
right = 0
while right < len(s):
# c 是将移入窗口的字符
c = s[right]
window[c] = window.get(c, 0) + 1
# 增大窗口
right += 1
# 进行窗口内数据的一系列更新
#...
#/*** debug 输出的位置 ***/
# print(f"window: [{left}, {right})")
#/********************/
# 判断左侧窗口是否要收缩
while left < right and "window needs shrink":
# d 是将移出窗口的字符
d = s[left]
window[d] -= 1
if window[d] == 0:
del window[d]
# 缩小窗口
left += 1
# 进行窗口内数据的一系列更新
#...
单调栈
def nextGreaterElement(nums):
stack = [] # 用于存储单调递增序列的栈
result = [0] * len(nums) # 初始化结果数组，所有元素先设为0（表示没有找到更大的元素）
for i in range(len(nums)):
# 当栈不为空且当前元素大于栈顶元素时，说明找到了一个比栈顶元素大的元素
while stack and nums[i] > nums[stack[-1]]:
# 将栈顶元素出栈，并更新结果数组
result[stack.pop()] = nums[i]
# 将当前元素索引入栈
stack.append(i)
# 处理右边没有更大元素的情况，将结果数组中未被更新的位置设为-1
return [x if x != 0 else -1 for x in result]
# 示例
nums = [1, 7, 5, 9, 2, 5]
print(nextGreaterElement(nums)) # 输出: [7, 9, 9, -1, 5, -1]
