# 单调栈的理论基础

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为 O (n)。

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。

更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。

在使用单调栈的时候首先要明确如下几点：

单调栈里存放的元素是什么？

单调栈里只需要存放元素的下标 i 就可以了，如果需要使用对应的元素，直接 T [i] 就可以获取。

单调栈里元素是递增呢？还是递减呢？

以下描述顺序从栈头到栈底的顺序。

如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

使用单调栈主要有三个判断条件：

当前遍历的元素 T [i] 小于栈顶元素 T [st.top ()] 的情况
当前遍历的元素 T [i] 等于栈顶元素 T [st.top ()] 的情况
当前遍历的元素 T [i] 大于栈顶元素 T [st.top ()] 的情况

# 每日温度

题目链接🔗

用 temperatures = [73, 74, 75, 71, 71, 72, 76, 73] 为例来逐步分析，输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

Alt text

加入 T [1] = 74，因为 T [1] > T [0]（当前遍历的元素 T [i] 大于栈顶元素 T [st.top ()] 的情况）。

我们要保持一个递增单调栈（从栈头到栈底），所以将 T [0] 弹出，T [1] 加入，此时 result 数组可以记录了，result [0] = 1，即 T [0] 右面第一个比 T [0] 大的元素是 T [1]。

Alt text

加入 T [2] = 75 同理，T [1] 弹出

Alt text

加入 T [3]，T [3] < T [2] （当前遍历的元素 T [i] 小于栈顶元素 T [st.top ()] 的情况），加 T [3] 加入单调栈。

Alt text

加入 T [4]，T [4] == T [3] （当前遍历的元素 T [i] 等于栈顶元素 T [st.top ()] 的情况），此时依然要加入栈，不用计算距离，因为我们要求的是右面第一个大于本元素的位置，而不是大于等于！

Alt text

加入 T [5]，T [5] > T [4] （当前遍历的元素 T [i] 大于栈顶元素 T [st.top ()] 的情况），将 T [4] 弹出，同时计算距离，更新 result。

Alt text

直到发现 T [5] 小于 T [st.top ()]，终止弹出，将 T [5] 加入单调栈

Alt text

加入 T [6]，同理，需要将栈里的 T [5]，T [2] 弹出

Alt text

同理，继续弹出

Alt text

此时栈里只剩下了 T [6]

Alt text

加入 T [7]， T [7] < T [6] 直接入栈，这就是最后的情况，result 数组也更新完了。

Alt text

	class Solution {
	public:
	vector<int> dailyTemperatures(vector<int>& T) {
	// 递增栈
	stack<int> st;
	vector<int> result(T.size(), 0);
	st.push(0);
	for (int i = 1; i < T.size(); i++) {
	if (T[i] <= T[st.top()]) { // 情况一和二
	st.push(i);
	} else {
	while (!st.empty() && T[i] > T[st.top()]) { // 情况三
	result[st.top()] = i - st.top();
	st.pop();
	}
	st.push(i);
	}
	}
	return result;
	}
	};

# 下一个更大元素 I

题目链接🔗

本题意思是说 nums1 是 nums2 的子集，找 nums1 中的元素在 nums2 中下一个比当前元素大的元素。

定义一个和 nums1 一样大小的数组 result 来存放结果，result 初始化为 - 1。

在遍历 nums2 的过程中，我们要判断 nums2 [i] 是否在 nums1 中出现过，因为最后是要根据 nums1 元素的下标来更新 result 数组。

因为两个数组没有重复元素，可以用 map 来做映射。根据数值快速找到下标，还可以判断 nums2 [i] 是否在 nums1 中出现过。

栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。

情况一：当前遍历的元素 T [i] 小于栈顶元素 T [st.top ()] 的情况

此时满足递增栈（栈头到栈底的顺序），所以直接入栈。

情况二：当前遍历的元素 T [i] 等于栈顶元素 T [st.top ()] 的情况

如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！

情况三：当前遍历的元素 T [i] 大于栈顶元素 T [st.top ()] 的情况

此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。

判断栈顶元素是否在 nums1 里出现过，（注意栈里的元素是 nums2 的元素），如果出现过，开始记录结果。

	class Solution {
	public:
	vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
	stack<int> st;
	vector<int> result(nums1.size(), -1);
	if (nums1.size() == 0) return result;

	unordered_map<int, int> umap; //key: 下标元素，value：下标
	for (int i = 0; i < nums1.size(); i++) {
	umap[nums1[i]] = i;
	}
	st.push(0);
	for (int i = 1; i < nums2.size(); i++) {
	if (nums2[i] <= nums2[st.top()]) { // 情况一和情况二
	st.push(i);
	} else { // 情况三
	while (!st.empty() && nums2[i] > nums2[st.top()]) {
	if (umap.count(nums2[st.top()]) > 0) { // 看 map 里是否存在这个元素
	int index = umap[nums2[st.top()]]; // 根据 map 找到 nums2 [st.top ()] 在 nums1 中的下标
	result[index] = nums2[i];
	}
	st.pop();
	}
	st.push(i);
	}
	}
	return result;
	}
	};

# 单调栈的理论基础

# 每日温度

# 下一个更大元素 I

【代码随想录Day38】动态规划 Part.11

【代码随想录Day40】单调栈 Part.2