【数据结构-栈 二】【单调栈】每日温度、接雨水

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【单调栈的应用】，使用【栈】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

每日温度【MID】

每日温度是单调栈的典型应用题

题干

解题思路

• 构造递减栈，寻找右侧第一个大于当前元素的数
• 遍历整个数组，如果栈不空，且当前数字大于栈顶元素，满足结算条件：所以需要取出栈顶元素进行结算，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。
• 继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来

初始化result的长度与原数组长度相同，如果后续无结果录入则自动补0

代码实现

给出代码实现基本档案

基本数据结构：栈
辅助数据结构：无
算法：无
技巧：单调栈

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型 the n* @return int整型*/public int[] dailyTemperatures(int[] temperatures) {// 1 入参判断，如果数组为空，则结果集为空数组if (temperatures == null || temperatures.length == 0) {return new int[temperatures.length];}// 2 定义单调递减栈，单调栈存储当前温度下标，和返回结果集Stack<Integer> singleStack = new Stack<Integer>();int[] result = new int[temperatures.length];// 3 遍历数组，进行温度结算for (int i = 0; i < temperatures.length; i++) {// 如果满足结算条件，进行结算while (!singleStack.isEmpty() && temperatures[i] > temperatures[singleStack.peek()]) {// 1 弹出并记录当前温度记录时间int cur = singleStack.pop();// 2 计算更大温度时间与当前温度时间差result[cur] = i - cur;}// 结算完毕后元素入栈singleStack.push(i);}return result;}}

复杂度分析

时间复杂度O(n)：虽然 while 循环里套了一个 while 循环，但是考虑到每个元素最多访问两次，入栈一次和出栈一次，所以时间复杂度是 O(n)。

空间复杂度O(n)：O(n)。栈的空间

接雨水【HARD】

千呼万唤始出来，经典题目接雨水，使用单调栈来解决

题干

计算蓝色雨水部分的单位数量

解题思路

原题解地址，单调栈就是保持栈内元素有序。和单调队列一样，需要我们自己维持顺序，没有现成的容器可以用。通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

1 问题的求解方向

而接雨水这道题目，我们正需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积，首先单调栈是按照行方向来计算雨水

2 单调栈的单调顺序

从大到小还是从小到大呢？从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子

3 遇到相同高度的柱子怎么办

如果遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出，把第二个5添加到栈中。因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度

4 栈里存什么

使用单调栈，也是通过 长 * 宽 来计算雨水面积的。长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，那么栈里有没有必要存一个pair<int, int>类型的元素，保存柱子的高度和下标呢。其实不用，栈里就存放下标就行，想要知道对应的高度，通过height[stack.top()] 就知道弹出的下标对应的高度了

所以栈的定义如下：

stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度

5 算法流程

以下逻辑主要就是三种情况

• 情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
• 情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
• 情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]
  先将下标0的柱子加入到栈中，st.push(0);。 栈中存放我们遍历过的元素，所以先将下标0加进来。

然后开始从下标1开始遍历所有的柱子，for (int i = 1; i < height.size(); i++)。如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。代码如下

if (height[i] < height[st.top()])  st.push(i);

如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。

if (height[i] == height[st.top()]) { // 例如 5 5 1 7 这种情况st.pop();st.push(i);
}

如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了

1. 取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]（就是图中的高度1）。
2. 此时的栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]（就是图中的高度2）。
3. 当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]（就是图中的高度3）。

此时应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的元素，三个元素来接水！

• 雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：int h = min(height[st.top()], height[i]) - height[mid];
• 雨水宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：int w = i - st.top() - 1 ;
• 当前凹槽雨水的体积就是：h * w。

求当前凹槽雨水的体积代码如下：

while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while，持续更新栈顶元素int mid = st.top();st.pop();if (!st.empty()) {int h = min(height[st.top()], height[i]) - height[mid];int w = i - st.top() - 1; // 注意减一，只求中间宽度sum += h * w;}
}

简化后的流程如下

继续结算5对应的雨水

4和6高度相同，无需结算，继续寻找高墙

寻找到高墙后继续结算

代码实现

给出代码实现基本档案

基本数据结构：栈
辅助数据结构：无
算法：无
技巧：单调栈

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** max water* @param arr int整型一维数组 the array* @return long长整型*/public long maxWater (int[] arr) {// 1 入参判断，数组为空，结算0个单位雨水if (arr == null || arr.length == 0) {return 0;}// 2 定义单调栈，存储元素下标,定义总的雨水单位Stack<Integer> singleStack = new  Stack<Integer>();int result = 0;// 3 遍历数组，进行雨水计算for (int i = 0; i < arr.length; i++) {// 右边的墙大于当前栈顶元素，满足结算条件，进行结算while (!singleStack.isEmpty() && arr[i] > arr[singleStack.peek()]) {// 1 当前栈顶元素出栈int bottom = singleStack.pop();// 如果当前栈顶只有一个元素，弹出后栈空，则无需结算，因为左边界没有墙无法蓄水if (singleStack.isEmpty()) {break;}// 2 bottom已弹出，此时的栈顶元素为左边墙,当前元素为右边界int left = singleStack.peek();int right = i;// 3 分别计算高度和宽度int height = Math.min(arr[left], arr[i]) - arr[bottom];int weight = i - left - 1;// 4 结算雨水单位并累加result += height * weight;}// 结算完毕后，继续存储单调递减元素singleStack.push(i);}return result;}
}

复杂度分析

时间复杂度O(n)：虽然 while 循环里套了一个 while 循环，但是考虑到每个元素最多访问两次，入栈一次和出栈一次，所以时间复杂度是 O(n)。

空间复杂度O(n)：O(n)。栈的空间

拓展知识：普通栈与单调栈

普通栈和单调栈都是数据结构，用于在计算机编程中处理和解决各种问题。它们的主要区别在于它们的行为方式和用途。

1. 普通栈（Regular Stack）：

   • 普通栈是一种基本的数据结构，遵循后进先出（Last-In-First-Out，LIFO）的原则。这意味着最后放入栈的元素将首先被弹出。
   • 普通栈通常用于存储和管理临时数据，如函数调用的上下文信息、表达式求值、括号匹配等。
   • 普通栈的操作包括压栈（push）和弹栈（pop），以及查看栈顶元素（top）。

2. 单调栈（Monotonic Stack）：

   • 单调栈是一种特殊类型的栈，它通常用于解决一类特定问题，其中需要维护一个特定的单调性。
   • 单调栈分为单调递增栈和单调递减栈两种类型。
   • 单调递增栈：栈内元素保持递增的顺序，新元素入栈时，会弹出比它小的元素。
   • 单调递减栈：栈内元素保持递减的顺序，新元素入栈时，会弹出比它大的元素。
   • 单调栈常用于解决一些与查找元素位置或计算区间最大/最小值相关的问题，如寻找下一个更大元素、寻找下一个更小元素、计算柱状图中每个柱子的最大矩形面积等问题。

单调栈的主要思想是利用栈来维护特定的单调性，以快速查找和处理与这种单调性相关的问题。普通栈则是一种通用的数据结构，没有特定的单调性要求，用途更广泛。