【算法】单调栈

leetcode刷题笔记，单调栈系列。

739.每日温度

题目

https://leetcode.cn/problems/daily-temperatures/

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

1 2	1 <= temperatures.length <= 105 30 <= temperatures[i] <= 100

思路

这是单调栈系列的入门题目，可以让我们很好的了解单调栈的特性。

首先，题目要求的是返回一个结果集（我一般定义为retV），结果集中的每一位是当前温度下一个比他大的温度在“几天后”，也就是在数组中相隔的举例。比如下标1的下一个比他大的温度是下标3，那么就是2天后，也可以用3-1这种下标相减的方式直接计算出来。

为了能直接更新出这个距离，我们需要一个栈，这个栈维护的是元素下标，概念是对应的元素在栈内是单调递增的（从栈顶到栈底）。

如果单调栈直接维护数组中的元素的话，我们就没有办法直接算出两个下标直接的距离得出相差的天数，那样就没有什么意义了。我们维护下标，相当于同时维护了一个“距离”和元素本身的值（毕竟下标可以从原数组中取出值来）。

当我们遍历i的时候，i之前的元素已经按栈顶到栈底升序的方式放入栈内了，我们取栈顶得到的一定是i之前的某一个元素的下标，当temperatures[i]比栈顶下标对应的元素temperatures[st.top()]的元素更大，说明i是栈顶元素之后第一个比他大的元素。此时就可以通过i-st.top()得出距离，写入到retV[st.top()]结果集中。

注意，这个判断操作是一个循环，因为我们当前的元素temperatures[i]可能会匹配很多之前元素的条件。比如数组2 1 3中，3就是比2和1都大的元素，此时2和1都需要把下一个比自己大的元素更新为3。

// 只要栈内有元素，就需要继续弹出，不断判断是否比栈顶元素大
while (!st.empty() &&
	   temperatures[i] > temperatures[st.top()])
{}

如果当temperatures[i]比栈顶下标对应的元素temperatures[st.top()]更小，此时只需要将i下标入栈，相当于维护了单调栈从栈顶到栈底单调递增的特性，继续后续的比较。

另外，题目要求如果某一天之后没有比他温度更高的，则在结果集中写为0。这个可以直接用vector的构造函数来把整个数组初始化为0。如果某一天之后没有比他温度更高的，在循环中就不会被赋值，保留了构造函数初始化的0，也符合题目的预期结果。

完整代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st; // 单调栈
        // 这里初试化为全0，默认每个元素右边都么有比自己大的，这样结尾的元素不需要单独处理
        vector<int> retV(temperatures.size(), 0);
        // 思路如下，遍历的时候，将下标入栈
        // 1.当前元素大于栈顶元素（用下标访问得到元素大小），出栈顶元素
        //   并使用当前元素下标-栈顶元素下标得到距离，写入结果集
        // 2.当前元素小于等于栈顶元素，将下标入栈
        //
        // 这样能保障栈顶到栈底是递增的，也就能找到右边第一个比当前元素大的元素
        // 第一个元素直接入栈
        st.push(0);
        // 从第二个元素开始遍历
        for (int i = 1; i < temperatures.size(); i++) {
            // 大于
            if (temperatures[i] > temperatures[st.top()]) {
                // 只要栈内有元素，就需要继续弹出，不断判断是否比栈顶元素大
                while (!st.empty() &&
                       temperatures[i] > temperatures[st.top()]) {
                    int topIndex = st.top();
                    st.pop();
                    retV[topIndex] = i - topIndex; // 赋值距离
                }
                // 栈为空，或者当前元素小于栈顶元素，可以入栈
                if (st.empty() || temperatures[i] <= temperatures[st.top()]) {
                    // cout << "push " << i << endl;
                    st.push(i);
                }
            } else // 小于等于
            {
                st.push(i);
            }
        }
        // 到这里遍历结束了，但是栈里面还有元素
        // 此时栈里面的元素右边都不会有比自己更大的元素了，因为从栈顶到栈底是递增的
        // 而我们在初始化vector的时候已经初始化为全0了，也就不需要对这种情况单独处理
        return retV;
    }
};

496. 下一个更大元素 I

题目

https://leetcode.cn/problems/next-greater-element-i/description/

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个比 x 大的元素。

给你两个没有重复元素的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的下一个更大元素。

示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

思路

这道题其实和739没有什么区别，但是我们得理清楚题目要求的是什么，以及nums1和nums2的含义。

nums1是nums2的子集，代表nums1的元素都可以在nums2中找到。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个比 x 大的元素。

这个描述的意思是，我们需要返回一个基于nums1的数组，数组中的每一个元素，是nums1[i]在nums2中对应的下一个比他大的元素。注意不再是下标距离了，而是下一个比他大的元素本身。

说白了就是，这道题让我们基于nums2找每一个元素下一个比他大的元素是谁。但是最终的结果集只需要包含nums1中存在的元素就可以了。

这样思路就简单了，我们可以用一个map来维护nums1中出现的元素和他们在nums1中对应的下标。方便在最终的结果集里面设置。然后直接和739题目一样遍历nums2就可以了。

// 使用map来映射1中的元素和1中的下标，方便设置结果
unordered_map<int, size_t> index1Map;
for (size_t i = 0; i < nums1.size(); i++) {
    index1Map[nums1[i]] = i;
}

你甚至可以先直接按739的方式把所有nums2元素的下一个比他更大的元素找出来存放到map里面，然后再遍历nums1把对应元素的下一个比他大的元素设置进结果集里面。这样本题和739想必就不存在逻辑代码的大的改变了。

完整代码

核心思路和739题目那是一样一样的。只不过在while循环中，我们需要判断当前栈顶元素是否出现在nums1中了，出现过才需要设置到结果集里面。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        // 题目说1和2数组都没有重复元素，意思是单个数组中没有重复的。
        // 注意，题目要求的是1中的元素，在2里面对应的下一个更大元素是谁
        // 本质上是让我们求2中的某一个元素的下一个更大元素是谁，这里的“某一个元素”被nums1固定了。
        // 所以结果的数量是nums1。
        vector<int> retV(nums1.size(), -1);
        // 使用map来映射1中的元素和1中的下标，方便设置结果
        unordered_map<int, size_t> index1Map;
        for (size_t i = 0; i < nums1.size(); i++) {
            index1Map[nums1[i]] = i;
        }
        // nums1只是一个给出的要找下一个更大元素的集合，真的要找的东西都在2里面，得遍历2。
        stack<int> st; // 同样是从栈顶到栈底单调递增的栈，存放2中的下标。
        st.push(0); // 第一个元素直接入栈
        for (size_t i = 1; i < nums2.size(); i++) {
            // 因为求的是下一个比当前元素大的，所以小于等于的都直接入栈
            if (nums2[i] <= nums2[st.top()]) {
                st.push(i);
            } else {
                // while循环一直判断是否比当前元素小
                while (!st.empty() && nums2[i] > nums2[st.top()]) {
                    // 判断这个栈顶元素是否被nums1选中需要处理
                    auto ret = index1Map.find(nums2[st.top()]);
                    if (ret != index1Map.end()) {
                        // 取下标
                        size_t indexIn1 = ret->second;
                        // 设置下一个更大的元素是谁（不是设置距离了）
                        retV[indexIn1] = nums2[i];
                    }
                    // 不管有没有被选中都须出栈
                    st.pop();
                }
                // 当前元素入栈
                st.push(i);
            }
        }
        return retV;
    }
};

这里顺带贴出上文提到过的把2中所有元素下一个比他大的元素弄出来再遍历nums1的方法

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        // 使用map来映射2中的元素下一个比他大的元素。
        unordered_map<int, int> biggerMap;
        // nums1只是一个给出的要找下一个更大元素的集合，真的要找的东西都在2里面，得遍历2。
        stack<int> st; // 同样是从栈顶到栈底单调递增的栈，存放2中的下标。
        st.push(0); // 第一个元素直接入栈
        for (size_t i = 1; i < nums2.size(); i++) {
            // 因为求的是下一个比当前元素大的，所以小于等于的都直接入栈
            if (nums2[i] <= nums2[st.top()]) {
                st.push(i);
            } else {
                // while循环一直判断是否比当前元素小
                while (!st.empty() && nums2[i] > nums2[st.top()]) {
                    biggerMap[nums2[st.top()]] = nums2[i];
                    st.pop();
                }
                // 当前元素入栈
                st.push(i);
            }
        }
        // 题目说1和2数组都没有重复元素，意思是单个数组中没有重复的，但是两个数组之间会有。
        // 注意，题目要求的是1中的元素，在2里面对应的下一个更大元素是谁
        // 本质上是让我们求2中的某一个元素的下一个更大元素是谁，这里的“某一个元素”被nums1固定了。
        // 所以结果的数量是nums1。
        vector<int> retV(nums1.size(), -1);
        // 重新遍历nums1，找map中该元素下一个比他大的元素是啥，设置进结果集里面
        for (size_t i = 0; i < nums1.size(); i++) {
            // 注意，有些元素不存在下一个比他更大的，此时不能直接[]取，会取出来int默认值0；
            if (biggerMap.count(nums1[i]) != 0) {
                int nextBigger = biggerMap[nums1[i]];
                retV[i] = nextBigger;
            }
        }
        return retV;
    }
};

效果都是一样的，也符合题目对时间复杂度的进阶要求

503. 下一个更大元素 II

题目

https://leetcode.cn/problems/next-greater-element-ii/description/

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。

数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

1 2	1 <= nums.length <= 104 -109 <= nums[i] <= 109

思路

这道题咋一看引入了循环数组，有点难，但实际上因为题目没有说让我们计算距离，可以直接把原本的数组弄成两份合并成一个大数组，然后用739题目的方式把这个大数组遍历完毕，就能得到每一个数的下一个更大的元素是什么了。

可以用如下的方式，构建一个目标数组，把原数组两次插入进去即可。

1 2	vector<int> nums1(nums.begin(), nums.end()); nums1.insert(nums1.end(), nums.begin(), nums.end());

但是这样做会有一个额外的O(N)的时间复杂度消耗，虽然最终我们的时间复杂度是定格在了O(2N)量级，但我们还是可以想办法把这个多出来的时间复杂度和空间复杂度给优化一下的。

解决方式如下，我们直接把for循环的遍历区间乘2，然后每一次模一下数组的长度来得到实际的下标，这样就模拟出了遍历两次nums数组了！

for (int k = 1; k < nums.size() * 2; k++) {
	int i = k % nums.size(); // 实际的下标
	// ...
}

后续的操作步骤和739题一模一样，此处不做讲解。

完整代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        // 这到题和739完全一样，只不过是循环数组；
        // 因为结果不需要我们写距离，而是记录元素，那么问题就很好解决了；
        // 我们可以把原本数组拼接一次，然后直接进行判断，再把判断结果resize为原数组大小即可。
        // vector<int> nums1(nums.begin(), nums.end());
        // nums1.insert(nums1.end(), nums.begin(), nums.end());
        // 但是这样会有额外的扩容拼接的消耗，我们还不如直接用for循环模拟两次遍历nums；
        stack<int> st;
        st.push(0); // 下标
        // 结果集
        vector<int> retV(nums.size(), -1);
        // 从1开始遍历
        for (int k = 1; k < nums.size() * 2; k++) {
            int i = k % nums.size(); // 实际的下标
            if (nums[i] <= nums[st.top()]) {
                st.push(i);
            } else {
                while (!st.empty() && nums[i] > nums[st.top()]) {
                    retV[st.top()] = nums[i];
                    st.pop();
                }
                st.push(i);
            }
        }
        return retV;
    }
};

42. 接雨水

题目

https://leetcode.cn/problems/trapping-rain-water/

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：

1
2
3

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

思路

这道题可是火热的很，面试笔试常考题，也是单调栈的经典题目。虽然它可以用双指针或暴力方式实现，但是暴力和双指针方法个人感觉比单调栈的思路还难理解，因为会有很多边界情况，真让面试上手写了估计会压力山大汗流浃背啥都写不出来。不如把单调栈的思路背熟了直接上去就是啪啪一顿敲。

首先还是要记住739题目这个单调栈的入门题目。来分析一下接雨水需要记录什么数据。根据图片，我们知道，接雨水需要记录一个左边界、右边界、以及凹槽的高度，这样才能用长乘宽计算出雨水的面积。

比如下面这个图中，雨水的面积是中间这一块蓝色区域。要计算这个凹槽的面积，我们需要得到左边和右边两个柱子的高度，还需要知道中间凹槽底部有多高。

高度依据木桶原理，2和3中取最小的2，还需要减去底部的高度1，得到最终的高度为1；
宽度使用3的下标减去2的下标，再减去1（因为我们只需要中间部分），得到宽度是1；

最终的结果是1*1=1，雨水的面积是1。

这是比较普遍的情况，但是还有没那么普遍的情况，比如示例一中图片中间如同俄罗斯方块的这个部分，它要怎么计算出面积呢？

别急，我们先来分解一下接雨水的三种情况，然后你就知道上面这个俄罗斯方块的面积是怎么算出来的了。

和739题目一样，接雨水需要一个从栈顶到栈底单调递增的栈，存放的是下标。因为我们需要通过下标相减得出凹槽的宽度，高度可以直接通过下标访问原数组得到。

每次判断的时候有三种情况：

当前遍历的元素小于栈顶元素，入栈；
当前遍历的元素大于栈顶元素，开始比较和计算凹槽的面积；
- 取栈顶元素作为凹槽底部高度，并弹出栈顶元素；
- 栈的第二个元素作为凹槽左侧边界，该元素不能弹出；
- 凹槽的高度：min(左侧边界,当前元素为右侧边界) - 凹槽底部高度；
- 凹槽的宽度：当前下标 - 左边界下标 - 1；
- 通过高度和宽度相乘计算出雨水面积，加到结果中；
- 这里需要注意，刚开始的时候栈里面只有一个元素，所以我们在取了栈顶元素之后还需要判断栈里面是否有其他元素才能继续取左侧边界。可能会出现有一个高度柱没有左边界构成不了凹槽的情况（题目的示例一就是这种情况，左侧和坐标边界是不算数的，装不了雨水）；
- 这是一个循环while (!st.empty() && height[i] > height[st.top()])，一直到当前元素不大于栈顶元素或栈为空了才退出循环，和739题目是一样的。
当前遍历的元素等于栈顶元素，将栈顶元素弹出后将当前元素下标入栈；

当前元素大于栈顶元素的情况已经写清楚了，来看看为啥当前元素等于栈顶元素的时候需要将栈顶元素弹出再入当前元素的下标。

见下图，当我们遍历到第二个高度为4的柱子的时候，栈顶元素就是第一个高度为4的柱子，此时这两个柱子之间是没有凹槽的，装不了雨水，后续我们要计算凹槽宽度的时候，也应该拿第二个高度为4的柱子来计算，通过下标计算宽度3-1-1=1，如果用第一个高度为4的柱子计算，宽度就会多一位，计算出来的体积就不对了。

所以，当我们遍历到下标1的时候，栈顶元素和当前遍历元素相同，需要把栈顶的下标0弹出，入新的下标1，才能让后续计算得到正确的结果。

另外再根据思路解释一下为什么取出左边界后不能将这个元素出栈吧。见示例一的图，我给他标出了下标。

当我们遍历到下标6的时候，当前元素的高度大于栈顶元素，需要开始计算体积了，此时操作如下

取栈顶元素（下标5）作为凹槽底部，高度为0，下标5出栈；
取栈顶元素（下标4）作为凹槽左侧，高度为1；
高度：min(height[4],height[6]) - height[5] = 1;
宽度：6 - 4 - 1 = 1；
面积：1 * 1 = 1；

此时一次计算就完成了，算是这这个俄罗斯方块的凸出来的那一部分。注意我们取出来的凹槽左侧高度（下标4）这个元素还是当前单调栈的栈顶，这个元素是不能出栈的，来看看下一次循环中的遍历会做什么吧！

首先是进入了“当前元素大于栈顶元素”这个if条件里面的while循环，此时当前元素已经不大于栈顶元素了（和栈顶元素相同），会终止这个循环，并将当前元素（下标6）入栈。

1	while (!st.empty() && height[i] > height[st.top()])

下一次遍历，下标7的高度是3，大于栈顶元素，再次命中“当前元素大于栈顶元素”的if条件，进入循环内：

取栈顶元素（下标6）作为凹槽底部，高度为1，下标6出栈；
取栈顶元素（下标4）作为凹槽左侧，高度为1；
高度：min(height[4],height[7]) - height[6] = 0;
宽度：7 - 4 - 1 = 2；
面积：0 * 2 = 0；

实际上这几个元素是构成不了一个凹槽的，因为底部和左边界的高度一致，计算出来的结果和预期相同，面积是0。然后继续if里面的while循环：

取栈顶元素（下标4）作为凹槽底部，高度为1，下标4出栈；
取栈顶元素（下标3）作为凹槽左侧，高度为2；
高度：min(height[3],height[7]) - height[4] = 1;
宽度：7 - 3 - 1 = 3；
面积：3 * 1 = 3；

此时就能看出来为什么下标4不能出栈了。如果在while循环中将其出栈，到这里的循环就会错误的将下标3（高度为2）作为凹槽底部的高度，结果就大错特错啦！

执行到这里，我们就算出来了俄罗斯方块长的这3 * 1的雨水面积，整个俄罗斯方块就搞定啦。

完整代码

完整代码如下，里面部分注释用英文是因为我写OJ的时候喜欢切成ENG语言避免不小心按shift导致输入法换来换去，所以就干脆用三脚猫英语写注释了。

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        // 栈里面存下标，栈顶到栈底单调递增
        st.push(0);
        int sum = 0;
        for (size_t i = 1; i < height.size(); i++) {
            auto& cur = height[i];
            // 1.direct push to stack
            if (cur < height[st.top()]) {
                st.push(i);
            }
            // 2.replace index of top
            else if (cur == height[st.top()]) {
                st.pop();
                st.push(i);
            }
            // 3.clac space of rain
            else {
                while (!st.empty() && cur > height[st.top()]) {
                    int bottomIndex = st.top();
                    st.pop();
                    // 注意刚开始的时候可能只有一个元素
                    if (!st.empty()) {
                        int leftIndex = st.top();
                        // 错误！左边的元素不能被pop掉，因为它可能是下一个凹槽要用的底部值！
                        // st.pop();
                        // 计算凹槽高度和宽度
                        int h =
                            min(height[leftIndex], cur) - height[bottomIndex];
                        int w = i - leftIndex - 1;
                        // 雨水体积
                        sum += h * w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};