在处理数组和链表相关问题时，双指针技巧是经常用到的，
双指针技巧主要分为两类：左右指针和快慢指针。

例如：2sum

滑动窗口

一种特殊的双指针方法。
滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组。

1. 初始化 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]