双指针

双指针（Two Pointers）是一种常用的数组、链表遍历技巧，利用两个指针在序列上移动，解决区间、子串、去重等问题。

常见应用场景

• 有序数组的两数之和/三数之和
• 快慢指针判断链表有环
• 滑动窗口求子数组/子串问题
• 原地去重、反转、合并等

典型算法1：有序数组的两数之和

给定有序数组 nums 和目标值 target，返回两个数的下标使其和为 target。

代码示例（Python）：

def twoSum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1

典型算法2：滑动窗口

用于求解最长无重复子串、最小覆盖子串等问题。

代码示例（Python）：

def lengthOfLongestSubstring(s):
    seen = {}
    left = res = 0
    for right, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1
        seen[c] = right
        res = max(res, right - left + 1)
    return res

---

单调队列

单调队列是一种队列，队列中的元素保持单调递增或递减，常用于滑动窗口中的最值问题。

应用场景

• 滑动窗口最大/最小值
• 动态维护区间最值

典型算法：滑动窗口最大值

给定一个长度为 n 的数组 nums 和窗口大小 k，求每个窗口的最大值。

思路：

• 用一个双端队列维护窗口内可能成为最大值的下标，队列头始终是当前窗口最大值下标。
• 每次新元素入队时，弹出队尾所有比它小的元素。
• 队头元素如果滑出窗口则弹出。

代码示例（Python）：

from collections import deque

def maxSlidingWindow(nums, k):
    q = deque()
    res = []
    for i, x in enumerate(nums):
        while q and nums[q[-1]] < x:
            q.pop()
        q.append(i)
        if q[0] <= i - k:
            q.popleft()
        if i >= k - 1:
            res.append(nums[q[0]])
    return res

---

单调栈

单调栈是一种栈结构，栈内元素保持单调递增或递减，常用于解决“下一个更大/小元素”类问题。

应用场景

• 下一个更大元素/下一个更小元素
• 柱状图最大矩形面积
• 维护区间单调性

典型算法：下一个更大元素

给定一个数组，输出每个元素右侧第一个比它大的元素，没有则为 -1。

代码示例（Python）：

def nextGreater(nums):
    res = [-1] * len(nums)
    stack = []
    for i in range(len(nums) - 1, -1, -1):
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        if stack:
            res[i] = stack[-1]
        stack.append(nums[i])
    return res

---

三者对比

技巧	结构	主要应用场景	典型问题	复杂度	适用数据结构
双指针	指针	区间、子串、去重等	两数之和、滑窗等	O(n)	数组/链表
单调队列	队列	区间最值、滑动窗口	滑动窗口最大值	O(n)	数组
单调栈	栈	下一个更大/小元素等	柱状图最大矩形等	O(n)	数组

• 双指针偏向遍历与区间问题，空间消耗低。
• 单调队列适合动态维护区间最值，常用于滑动窗口。
• 单调栈适合处理“下一个更大/小元素”及区间单调性问题。

三者联系

• 三者本质上都是线性结构上的高效遍历与维护技巧，常用于数组、链表等顺序结构。
• 单调队列和单调栈都可以看作是双指针思想的进阶：
  • 单调队列通过队首队尾指针动态维护窗口区间的最值。
  • 单调栈通过栈顶指针动态维护区间单调性和下一个更大/小元素。
• 滑动窗口问题常常结合双指针和单调队列一起使用，提升效率。
• 三者都能将暴力 O(n^2) 问题优化为 O(n) 线性复杂度，是竞赛和面试中的常用套路。

三者既有区别也有联系，灵活组合能高效解决各类区间、最值、单调性相关问题。