一、单调栈

单调栈（Monotonic Stack）是一种特殊的栈结构，其核心思想是维护栈内元素的单调性（单调递增或单调递减）。单调栈通常用于解决与元素大小关系相关的问题，例如：

1. 找到数组中每个元素的下一个更大（或更小）元素。

2. 计算数组中每个元素左边或右边的第一个更大（或更小）元素。

3. 解决与区间最值相关的问题（如最大矩形面积）。

二、特点

1. 单调性：栈内元素始终保持单调递增或单调递减。

2. 操作规则：

   如果新元素满足单调性，直接压入栈。

如果新元素破坏了单调性，则弹出栈顶元素，直到满足单调性为止。

3. 时间复杂度：由于每个元素最多入栈和出栈一次，因此时间复杂度通常为O(n)

三、应用场景

1. 下一个更大元素：
   
   给定一个数组，找到每个元素的下一个更大元素。

2. 每日温度：
   
   给定一个温度数组，计算每天需要等待多少天才能遇到更高的温度。

3. 最大矩形面积：
   
   给定一个柱状图，计算其中最大的矩形面积。

4. 滑动窗口最大值：
   
   在滑动窗口中快速找到最大值。

四、步骤

以找到数组中每个元素的下一个更大元素为例：

1. 初始化：创建一个空栈和一个结果数组。

2. 遍历数组：

• 如果当前元素大于栈顶元素，则栈顶元素的下一个更大元素就是当前元素。

• 弹出栈顶元素，并更新结果数组。

• 重复上述过程，直到当前元素小于等于栈顶元素或栈为空。

• 将当前元素压入栈。

3. 处理剩余元素：遍历结束后，栈中剩余的元素没有下一个更大元素，将其结果设置为 -1。

对于滑动窗口第二类：窗口大小可变类型 

图解如下，类似双指针算法。

【解题思想】

1. 1、字符串 S 中使用双指针的左右指针技巧，初始化 left = right = 0，把索引的左闭右开区间 [left,right) 称为一个「窗口」。

2. 2、先不断增加 right 指针扩大窗口[left, right)（也就是 right++），直到窗口中的字符串符合要求：包含 T 中所有字符。

3. 3、停止增加 right ，转而不断增加 left 指针缩小窗口[left, right)（也就是 left++），直到窗口中的字符串不再符合要求：不包含 T 中所有字符。

4. 4、同时，每增加 left，都要更新一轮结果。

5. 5、重复 2 & 3 步骤，直到 right 到达字符串 S 的尽头。

6. 6、第 2 步骤寻找「可行解」（符合要求），第 3 步骤优化「可行解」（找最短），最终找到「最优解」（最短的覆盖子串）。

7. 7、左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」名字的来历。

一、定义

滑动窗口算法（Sliding Window Algorithm）是一种用于解决数组或字符串中子数组或子串问题的优化技术。它通过维护一个窗口（通常是数组或字符串的一个连续子区间），在遍历过程中动态调整窗口的起始和结束位置，从而高效地解决问题。

滑动窗口的核心思想是：

• 窗口大小固定：窗口的大小在滑动过程中保持不变。

• 窗口大小可变：窗口的大小根据条件动态调整。

二、使用场景

滑动窗口算法通常用于以下场景：

1. 1.子数组/子串问题：

• 求满足条件的最大或最小子数组/子串。

• 例如：最大子数组和、最小覆盖子串、最长无重复字符子串等。

2. 2.固定窗口大小问题：

• 例如：计算大小为 k 的子数组的平均值。

3. 3.优化暴力解法：

• 将时间复杂度从 O(n²) 优化到 O(n)。

三、示例

1.例题1：固定窗口大小

【题目描述】给定一个数组和一个整数 k，计算所有大小为 k 的子数组的平均值。

【题目分析】

（1） 什么是子数组？

• 子数组是数组中连续的一段元素。

• 例如，数组 [1, 3, 2, 6, -1] 的子数组包括 [1, 3, 2]、[3, 2, 6] 等。

（2）什么是大小为 k 的子数组？

• 大小为 k 的子数组是指长度为 k 的连续子数组。

• 例如，如果 k = 3，那么子数组的长度必须是 3。

（3）什么是子数组的平均值？

• 子数组的平均值是指子数组中所有元素的和除以子数组的长度。

• 例如，子数组 [1, 3, 2] 的平均值是 (1 + 3 + 2) / 3 = 2。

（4）问题的目标

• 对于数组中的每一个大小为 k 的子数组，计算其平均值，并返回所有平均值的集合。

【解题思路】

（1）暴力解法

• 遍历数组，对于每一个起始位置 i，计算从 i 到 i + k - 1 的子数组的和，然后除以 k 得到平均值。

• 时间复杂度：O(n * k)，其中 n 是数组的长度。

（2）滑动窗口优化

• 使用滑动窗口技术，避免重复计算子数组的和。

• 初始化第一个窗口的和，然后在滑动窗口时，加上新元素，减去旧元素。

• 时间复杂度：O(n)。

#include <iostream>  using namespace std;  void sw(int nums[], int n, int k) {      if (n < k) return; // 如果数组长度小于k，直接返回      double windowSum = 0;      // 初始化窗口      for (int i = 0; i < k; i++) {          windowSum += nums[i];      }      cout << windowSum / k << " ";      // 滑动窗口      for (int i = k; i < n; i++) {          windowSum += nums[i] - nums[i - k]; // 加上新元素，减去旧元素          cout << windowSum / k << " ";      }      cout << endl;  }    int main() {      int nums[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};      int n = sizeof(nums) / sizeof(nums[0]);      int k = 5;      sw(nums, n, k);      return 0;  }

【过程解释】

1. 初始化窗口：

• 计算第一个窗口的和 windowSum，即 nums[0] 到 nums[k-1] 的和。

• 输出第一个窗口的平均值 windowSum / k。

2. 滑动窗口：

• 从第 k 个元素开始，滑动窗口。

• 每次滑动时，加上新元素 nums[i]，减去旧元素 nums[i - k]。

• 输出当前窗口的平均值 windowSum / k。

图示：

第一次：（1+3+2）/3 

第二次：(3+2+6)/3 ，对比上一次，少了第一个数1，多了后一个数6

第二次：(2+6-1)/3 ，对比上一次，少了上一个数2，多了后一个数-1

【题目描述】

输入一个n×n的黑白图像（1表示黑色，0表示白色），任务是统计其中黑色连通块的个数。如果两个黑格子有公共边或者公共顶点，就说它们属于同一个联通块。如下图所示的图形有3个联通块。

【输入描述】

【输出描述】

【样例输入】

6  100100  001010  000000  110000  111000  010100

【样例输出】

3

【题目描述】

起点与终点相隔4500米。现Charley 需要从起点骑车到终点。但是，他有个习惯，沿途需要有人陪伴，即以相同的速度， 与另外一个人一起骑。而当他遇到以更快的速度骑车的人时，他会以相应的速度跟上这个更快的人。先给定所有与Charley 同路的人各自的速度与出发时间，问Charley 以这种方式跟人，骑完4500米需要多少时间。得出的结果若是小数，则向上取整。

【输入描述】

【输出描述】

【样例输入】

4  20 0  25 -155  27 190  30 240  2  21 0  22 34  0

【样例输出】

780  771

【题目描述】

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。



给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

【输入描述】

第一行是两个整数，R和C，代表迷宫的行数和列数。（ 1<= R，C <= 40)



接下来是R行，每行C个字符，代表整个迷宫。空地格子用’.‘表示，有障碍物的格子用’#‘表示。迷宫左上角和右下角都是’.’。

【输出描述】

【样例输入】

5 5  ..###  #....  #.#.#  #.#.#  #.#..

【样例输出】

9

【题目描述】

A城市有一条非常特别的街道，该街道在每个公里的节点上都有一个公交车站，乘客可以在任意的公交站点上车，在任意的公交站点下车。乘客根据每次乘坐公交的公里数进行付费，比如，下表就是乘客乘坐不同的公里数要付的费用。（请注意：不一定公里数越高，费用越高，这也是这条街道特别的地方）

一辆公交车单次行驶的公里数一定不超过10公里，一个乘客如果打算乘坐公交车完成n公里（1<=n<=100）的行程，他可以选择无限次的换车来完成行程。

请问，他最少要花多少钱？

【输入描述】

 第一行十个整数分别表示公交行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。

第二行一个整数n表示，旅客的总路程数。 （1<=n<=100）

【输出描述】

【样例输入】

12 21 31 40 49 58 69 79 90 101  15

【样例输出】

147

【题目描述】

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

【输入描述】

第一行是一个整数T，代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

【输出描述】

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

【样例输入】

2  2 2  1 1  3 4  2 3  2 3 4  1 6 5

【样例输出】

8  16

【数据范围】

1 ≤ T ≤ 100,

1 ≤ R, C ≤ 100,

0 ≤ M ≤ 1000

【题目描述】

Hello Kitty又一次来到花生地里摘花生，从左上角进入花生地，从右下角出去，只能向右或者向下，请问Hello Kitty应该沿着什么样的路线走，能够摘到的花生数量最多（假设花生地里没有任何2株的花生一样多，也不存在多条路线能够摘到一样多的花生的情况）？

比如输入：

2 2

1 2

3 4

应该输出：1-3-4，也就是按照1 3 4这三株数量的花生摘过去，能够摘到最多的花生！

【输入描述】

第一行是2个整数m和n（2=<m,n<=100），代表花生地有m行，n列花生！

后面m行，每行有n个整数代表了每行中，每株花生的数量

【输出描述】

【样例输入】

2 2  1 2   3 4

【样例输出】

1-3-4