break algorithm---刷题map

---

---

---

资源参考：
LeetCode
中文版：https://leetcode-cn.com/problemset/all/
英文版：https://leetcode.com/problemset/all/

相关代码实现 – python语言：
https://github.com/muxintong/break-algorithm/

LeetCode题解总结
https://github.com/labuladong/fucking-algorithm
https://labuladong.gitee.io/algo/
https://grandyang.com/leetcode/1147/

Python3文档
https://docs.python.org/3/

数据结构
https://www.runoob.com/data-structures/
Problem Solving with Algorithms and Data Structures using Python
https://runestone.academy/runestone/books/published/pythonds/index.html

---

---

---

一.单调栈

• 1.1 单调栈介绍
• 1.2 代表题目
  • 1.2.1 每日温度（739）
  • 1.2.2 去除重复字母（316）
  • 1.2.3 滑动窗口最大值（239_困难_O（n）时间复杂度解决）
  • 1.2.4 最大矩形（85）
  • 1.2.5 下一个更大元素II（503）
  • 1.2.6 柱状图中最大矩形（84_困难）
  • 1.2.7 接雨水（42_困难_性能敏感）
  • 1.2.8 股票价格跨度（901）

二.并查集

• 2.1 并查集介绍
• 2.2 代表题目
  • 2.2.1 朋友圈（547）
  • 2.2.2 冗余连接（684）
  • 2.2.3 岛屿数量（200_必做）
  • 2.2.4 句子相似性II (737_会员)
  • 2.2.5 得分最高的路径（1102_会员）
  • 2.2.6 最低成本联通所有城市（1135_会员）
  • 2.2.7 以图辨树（261_会员）
  • 2.2.8 按字典序排列最小的等效字符串（1061_会员）
  • 2.2.9 无向图中连通分量的数目（323_会员）
  • 2.2.10 尽量减少恶意软件的传播（924_困难）

三.滑动窗口

• 3.1 滑动窗口介绍
• 3.2 代表题目
  • 3.2.1 尽可能使字符串相等（1208）
  • 3.2.2 长度最小的子数组（209）
  • 3.2.3 无重复字符的最长子串（3）
  • 3.2.4 最大连续1的个数 III (1004)
  • 3.2.5 至多包含 K 个不同字符的最长子串（340_会员_困难）
  • 3.2.6 最少交换次数来组合所有的 1（1151_会员）
  • 3.2.7 至多包含两个不同字符的最长子串（159_会员）
  • 3.2.8 长度为 K 的无重复字符子串（1100_会员）
  • 3.2.9 最小覆盖子串（76）
  • 3.2.10 字符串排列（567）
  • 3.2.11 找所有字母异位词（438）

四.前缀和 & HASH

• 4.1 前缀和 & HASH介绍
• 4.2 代表题目
  • 4.2.1 和为K的子数组（560）
  • 4.2.2 连续的子数组和（523）
  • 4.2.3 和可被 K 整除的子数组（974）

五.差分

• 5.1 差分
• 5.2 代表题目
  • 5.2.1 拼车（1094）
  • 5.2.2 航班预订统计（1109）
  • 5.2.3 买卖股票的最佳时机（121_简单）
  • 5.2.4 买卖股票的最佳时机II（122）
  • 5.2.5 会议室 II （253_会员）
  • 5.2.6 等差数列划分 （413）

六.拓扑排序

• 6.1 拓扑排序介绍
• 6.2 代表题目
  • 6.2.1 课程表 II（610）
  • 6.2.2 序列重建（444_会员）
  • 6.2.3 火星词典（269）

七.字符串

• 7.1 前缀和 & HASH介绍
• 7.2 代表题目
  • 7.2.1 最长回文子串（5）
  • 7.2.2 复原IP地址（93-dfs）
  • 7.2.3 字符串相乘（43）
  • 7.2.4 基本计算器 II（227）

八.BFS

• 8.1 BFS介绍
• 8.2 代表题目
  • 8.2.1 单词接龙（127）
  • 8.2.2 单词拆分（139）
  • 8.2.3 被围绕的区域（130）
  • 8.2.4 离建筑物最近的距离（317）
  • 8.2.5 迷宫 II （505_会员）
  • 8.2.6 扫雷游戏 （529）
  • 8.2.7 推箱子（1263）
  • 8.2.8 进击的骑士（1197_会员）
  • 8.2.9 公交路线 （815）
  • 8.2.10 最短的桥 （934）

九.DFS

• 9.1 DFS介绍
• 9.2 代表题目
  • 9.2.1 最短的桥（934）
  • 9.2.2 得分最高的路径（1102_会员）
  • 9.2.3 冗余连接 II（685）
  • 9.2.4 孤独像素 I（531_会员）
  • 9.2.5 孤独像素 II （533_会员）
  • 9.2.6 重新安排行程 （332）
  • 9.2.7 打家劫舍 III（337）
  • 9.2.8 路径总和 II（113）

十.动态规划

• 10.1 动态规划介绍
• 10.2 代表题目
  • 10.2.1 打家劫舍 II（213）
  • 10.2.2 分隔数组以得到最大和（1043）
  • 10.2.3 分割等和子集（416）
  • 10.2.4 买卖股票的最佳时机 III（123）
  • 10.2.5 不同路径（62）
  • 10.2.6 不同路径 II （63）
  • 10.2.7 4键键盘（651_会员）
  • 10.2.8 轰炸敌人（361）
  • 10.2.9 校园自行车分配 II（1066_会员）
  • 10.2.10 角矩形的数量（750_会员）
  • 10.2.11 抛掷硬币（1230）
  • 10.2.12 形成字符串的最短路径（1055_会员）

十一.贪心算法

• 11.1 贪心算法介绍
• 11.2 代表题目
  • 11.2.1 用最少数量的箭引爆气球（452）
  • 11.2.2 分享巧克力（1231_会员）
  • 11.2.3 交换字符使得字符串相同（1247）
  • 11.2.4 跳跃游戏 II（45）
  • 11.2.5 任务调度器（621）
  • 11.2.6 摆动序列（376）

十二.字典树

• 12.1 字典树介绍
• 12.2 代表题目
  • 12.2.1 单词的压缩编码（820）
  • 12.2.2 分享巧克力（1231_会员）
  • 12.2.3 单词替换（648）
  • 12.2.4 实现 Trie (前缀树)（208）

---

---

---

---

一.单调栈

1.1 单调栈介绍

单调栈：

1. 定义：栈内元素单调递增或者单调递减的栈，单调栈只能在栈顶操作。
   单调栈 = 单调 + 栈，因此其同时满足两个特性: 单调性、栈的特点。
   单调性: 单调栈里面所存放的数据是有序的(单调递增或递减)。
   栈: 后进先出。
2. 实现：单调栈里的元素具有单调性，元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除。
   单调递减栈：找到从左起第一个比当前元素大的元素

	stack<int> st;
	for (遍历这个数组)
	{
    
		if (栈空 || 栈顶元素大于等于当前比较元素)
		{
    
			入栈;
		}
		else
		{
    
			while (栈不为空 && 栈顶元素小于当前元素)
			{
    
				栈顶元素出栈;
				更新结果;
			}
			当前数据入栈;
		}
	}

上述代码优化合并：

stack<int> st;
for(遍历数组）{
    
	while（当前元素 > 栈顶元素 && 栈非空）{
    
		弹栈；//catch it！找到了从左起第一个比当前元素大的元素！
		更新结果集；
	}
	当前元素入栈；
}

单调递增栈：找到从左起第一个比当前元素小的元素

stack<int> st;
for(int i=0; i<arr.length; i++){
    
	while(当前元素 < 栈顶元素 && 栈非空）{
    
		弹栈；//catch it！找到了从左起第一个比当前元素小的元素！
		更新结果集；
	}
	当前元素入栈；
}

3. 时间复杂度：O(n)
   线性，每个元素遍历一次。
   因其满足单调性和每个数字只会入栈一次，并且出栈后再也不会进栈了，所以可以在时间复杂度 O(n) 的情况下解决一些问题。
4. 应用：
   - 单调递增栈可以找到左起第一个比当前数字小的元素
   - 单调递减栈可以找到左起第一个比当前数字大的元素