Chuoer47's Blog

Appearance

本文转载自力扣讨论区，作者：灵茶山艾府（endlesscheng）。 原文链接：https://leetcode.cn/circle/discuss/9oZFK9/

单调栈题单 单调栈入门 单调栈题目 单调栈教程 leetcode单调栈 灵茶山艾府 灵神 灵神题单

他向远方望去，无法看到高山背后的矮山，只看到一座座更高的山峰。

推荐先做做 数据结构题单 中的「枚举右，维护左」以及第三章「栈」的基础题目后，再来刷本题单。

一、单调栈 ​

§1.1 基础 ​

原理讲解：单调栈【基础算法精讲 26】

模板：

py
# 返回 left，其中 left[i] 是 nums[i] 左侧最近的严格大于 nums[i] 的数的下标，若不存在则为 -1
# 时间复杂度 O(len(nums))
def left_greater(nums: list[int]) -> list[int]:
    n = len(nums)
    left = [-1] * n
    st = []
    for i, x in enumerate(nums):
        while st and nums[st[-1]] <= x:  # 如果求严格小于，改成 >=
            st.pop()
        if st:
            left[i] = st[-1]
        st.append(i)
    return left

# 返回 right，其中 right[i] 是 nums[i] 右侧最近的严格大于 nums[i] 的数的下标，若不存在则为 len(nums)
# 时间复杂度 O(len(nums))
def right_greater(nums: list[int]) -> list[int]:
    n = len(nums)
    right = [n] * n
    st = []
    for i in range(n - 1, -1, -1):
        x = nums[i]
        while st and nums[st[-1]] <= x:  # 如果求严格小于，改成 >=
            st.pop()
        if st:
            right[i] = st[-1]
        st.append(i)
    return right
java
class Solution {
    // 返回 left，其中 left[i] 是 nums[i] 左侧最近的严格大于 nums[i] 的数的下标，若不存在则为 -1
    // 时间复杂度 O(nums.length)
    private int[] leftGreater(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        st.push(-1); // 哨兵
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (st.size() > 1 && nums[st.peek()] <= x) { // 如果求严格小于，改成 >=
                st.pop();
            }
            left[i] = st.peek();
            st.push(i);
        }
        return left;
    }

    // 返回 right，其中 right[i] 是 nums[i] 右侧最近的严格大于 nums[i] 的数的下标，若不存在则为 nums.length
    // 时间复杂度 O(nums.length)
    private int[] rightGreater(int[] nums) {
        int n = nums.length;
        int[] right = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        st.push(n); // 哨兵
        for (int i = n - 1; i >= 0; i--) {
            int x = nums[i];
            while (st.size() > 1 && nums[st.peek()] <= x) { // 如果求严格小于，改成 >=
                st.pop();
            }
            right[i] = st.peek();
            st.push(i);
        }
        return right;
    }
}
cpp
// 返回 left，其中 left[i] 是 nums[i] 左侧最近的严格大于 nums[i] 的数的下标，若不存在则为 -1
// 时间复杂度 O(nums.size())
vector<int> left_greater(vector<int>& nums) {
    int n = nums.size();
    vector<int> left(n);
    stack<int> st;
    st.push(-1); // 哨兵
    for (int i = 0; i < n; i++) {
        int x = nums[i];
        while (st.size() > 1 && nums[st.top()] <= x) { // 如果求严格小于，改成 >=
            st.pop();
        }
        left[i] = st.top();
        st.push(i);
    }
    return left;
}

// 返回 right，其中 right[i] 是 nums[i] 右侧最近的严格大于 nums[i] 的数的下标，若不存在则为 nums.size()
// 时间复杂度 O(nums.size())
vector<int> right_greater(vector<int>& nums) {
    int n = nums.size();
    vector<int> right(n);
    stack<int> st;
    st.push(n); // 哨兵
    for (int i = n - 1; i >= 0; i--) {
        int x = nums[i];
        while (st.size() > 1 && nums[st.top()] <= x) { // 如果求严格小于，改成 >=
            st.pop();
        }
        right[i] = st.top();
        st.push(i);
    }
    return right;
}
go
// 返回 left，其中 left[i] 是 nums[i] 左侧最近的严格大于 nums[i] 的数的下标，若不存在则为 -1
// 时间复杂度 O(len(nums))
func leftGreater(nums []int) []int {
	n := len(nums)
	left := make([]int, n)
	st := []int{-1} // 哨兵
	for i, x := range nums {
		for len(st) > 1 && nums[st[len(st)-1]] <= x { // 如果求严格小于，改成 >=
			st = st[:len(st)-1]
		}
		left[i] = st[len(st)-1]
		st = append(st, i)
	}
	return left
}

// 返回 right，其中 right[i] 是 nums[i] 右侧最近的严格大于 nums[i] 的数的下标，若不存在则为 len(nums)
// 时间复杂度 O(len(nums))
func rightGreater(nums []int) []int {
	n := len(nums)
	right := make([]int, n)
	st := []int{n} // 哨兵
	for i := n - 1; i >= 0; i-- {
		x := nums[i]
		for len(st) > 1 && nums[st[len(st)-1]] <= x { // 如果求严格小于，改成 >=
			st = st[:len(st)-1]
		}
		right[i] = st[len(st)-1]
		st = append(st, i)
	}
	return right
}

§1.2 进阶 ​

思维扩展：

二、矩形 ​

思维扩展：

三、贡献法 ​

思维扩展：

四、最小字典序 ​

关联题单 ​

算法题单 ​

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。