代码随想录Day 48|单调栈，leetcode题目：739. 每日温度、496.下一个更大元素 I、503.下一个更大元素II
提示：DDU，供自己复习使用。欢迎大家前来讨论~
文章目录
- 题目
- 题目一：739. 每日温度
- 解题思路：
- 暴力解法
- 单调栈
- 单调栈细节
- 题目二： 496.下一个更大元素 I
- 解题思路：
- 单调栈的设置
- 处理的三种情况
- 题目三：503.下一个更大元素II
- 解题思路：
- 1. 直接拼接数组
- 2. 模拟循环遍历
- 总结
- 核心思想
- 注意事项
- 性能
单调栈Part01
题目
题目一：739. 每日温度
739. 每日温度
解题思路：
暴力解法
两层for循环，把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)
单调栈
单调栈是一种高效的数据结构，用于处理与**单调性（递增或递减）**相关的数组问题：
-
应用场景：
- 寻找一维数组中每个元素右边或左边第一个比它大（或小）的元素。
- 处理下一个更大（或更小）元素的问题。
-
时间复杂度：
- 单调栈可以在 O(n) 时间复杂度内解决上述问题，其中 n 是数组的长度。
-
原理：
- 利用栈来维护一个递增（或递减）的序列。
- 遍历数组时，不断将元素推入栈中，直到遇到一个元素使得栈顶元素不满足单调性，此时弹出栈顶元素，并记录相关位置信息。
-
空间换时间：
- 使用栈来存储遍历过的元素，以便快速访问和处理。
-
实现过程：
- 遍历数组，对于每个元素，利用栈维护一个单调递增（或递减）的序列。
- 当前元素比栈顶元素大（或小），则继续推入栈中。
- 否则，弹出栈顶元素，并进行相应的操作（如记录索引、更新数据等），直到栈顶元素再次满足单调性。
-
优点：
- 只需遍历一次数组，即可找到所有元素的下一个更大（或更小）元素。
-
使用条件：
- 当问题涉及到查找数组中元素的相对顺序关系，且这种关系可以通过单调性来确定时，可以考虑使用单调栈。
单调栈细节
-
明确栈中存放的内容：
- 单调栈中存放的是数组元素的下标，而不是元素值本身。通过下标可以直接访问数组中的元素。
-
栈的单调性：
-
根据问题的需求，单调栈可以是递增的也可以是递减的。
-
递增单调栈：用于寻找每个元素右侧第一个更大的元素。
-
递减单调栈：用于寻找每个元素右侧第一个更小的元素。
-
-
判断条件：
- 小于栈顶元素：当前元素
T[i]小于栈顶元素T[st.top()]时，栈顶元素的右侧更大（或更小，取决于递增或递减）的元素就是T[i]。此时，可以执行相应的操作（如记录结果），然后将栈顶元素弹出。 - 等于栈顶元素：通常，如果当前元素等于栈顶元素，继续保留栈顶元素，因为它可能与后续更大的元素匹配。
- 大于栈顶元素：如果当前元素大于栈顶元素，说明栈顶元素不可能再与后续元素匹配，应继续压栈。
- 小于栈顶元素：当前元素
-
工作过程：
- 遍历数组，根据上述判断条件，决定是将当前元素的下标压入栈中，还是弹出栈顶元素，并记录所需的信息。
- 通过这种方式，可以在单次遍历中为每个元素找到其右侧的第一个更大（或更小）的元素。
单调栈的本质是利用栈来维护一个递增（或递减）序列，确保在遍历过程中能够快速确定元素间的相对顺序关系。
示例题目：
对于数组 temperatures = [73, 74, 75, 71, 71, 72, 76, 73]，想找到每个元素后面第一个更高的温度的索引与当前索引的差值。如果后面没有更高的温度，则差值为0。以下是单调栈的应用来解决这个问题：
- 初始化一个空栈，用于存储尚未找到更高温度的元素的索引。
- 初始化一个结果数组
res，长度与temperatures相同，并将所有元素初始化为0。这个数组将存储每个元素后面第一个更高温度的索引差值。 - 遍历
temperatures中的每个元素：- 对于每个温度值，只要栈不为空且当前温度高于栈顶索引对应的温度值，就弹出栈顶元素，并将
res数组中栈顶索引对应的位置更新为当前索引与栈顶索引的差值。 - 将当前索引压入栈中，因为尚未找到更高的温度。
- 对于每个温度值，只要栈不为空且当前温度高于栈顶索引对应的温度值，就弹出栈顶元素，并将
按照这个方法，逐步分析 temperatures 数组：
- 遍历到 73，栈为空，压入栈。
- 遍历到 74，高于栈顶（73），栈顶出栈，
res[0] = 1，然后压入栈。 - 遍历到 75，高于栈顶（74），栈顶出栈，
res[1] = 1，然后压入栈。 - 遍历到 71，低于栈顶（75），压入栈。
- 遍历到第二个 71，与前一个 71 相同，不改变
res数组，压入栈。 - 遍历到 72，低于栈顶（71），压入栈。
- 遍历到 76，高于栈顶（72, 71, 71, 73），依次弹出，更新
res[5] = 1，res[3] = 2，res[2] = 4，res[0] = 0（因为76是数组最后一个温度，没有更高的温度了），然后压入栈。 - 遍历到 73，低于栈顶（76），压入栈。
最终，得到 res = [1, 1, 4, 2, 1, 1, 0, 0]，这就是输出结果。
C++代码如下：
// 版本一
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 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;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
题目二： 496.下一个更大元素 I
496. 下一个更大元素 I
解题思路：
-
在“每日温度”问题中，单个数组内的元素相互比较。
-
在本问题中，是两个数组间的元素比较，且
nums1元素必须在nums2中找到对应的更大元素。 -
本题中使用了
unordered_map来存储nums1中元素的索引，以便快速查找和映射结果。
- 逻辑复杂性：
- “每日温度”问题相对简单，直接处理单个数组。
- 本问题需要额外处理两个数组间的关系，并通过映射来更新结果数组。
- 结果数组的初始化：
- 两题的结果数组都初始化为
-1，表示如果没有找到符合条件的更大元素，则输出为-1。
- 两题的结果数组都初始化为
- 遍历和条件判断：
- 在本问题中，需要额外判断
nums2[i]是否在nums1中出现过，这增加了处理的复杂性。
- 在本问题中，需要额外判断
那么预处理代码如下:
unordered_map<int, int> umap; // key:下标元素，value：下标
for (int i = 0; i < nums1.size(); i++) {
umap[nums1[i]] = i;
}
使用单调栈，首先要想单调栈是从大到小还是从小到大。
单调栈的设置
- 栈的顺序：栈应该保持递增顺序，即从栈顶到栈底元素逐渐增大。这样的顺序帮助我们找到每个元素右边第一个比自己大的元素。
处理的三种情况
- 情况一：当前元素小于栈顶元素
- 描述：当遍历到的元素
T[i]小于栈顶元素T[st.top()]时，说明当前元素不可能是栈顶元素的右边第一个更大的元素。 - 操作：将当前元素的索引入栈。
- 描述：当遍历到的元素
- 情况二：当前元素等于栈顶元素
- 描述：当
T[i]等于T[st.top()]时，这意味着当前元素与栈顶元素相同。 - 操作：仍然将当前元素索引入栈。这是因为我们只关心第一个更大的元素，相等的元素不会影响这一目标。
- 描述：当
- 情况三：当前元素大于栈顶元素
- 描述：当
T[i]大于T[st.top()]时，表明找到了栈顶元素的右边第一个更大的元素。 - 操作：
- 弹出栈顶元素，因为已经找到其右边第一个更大的元素（即当前元素
T[i]）。 - 检查弹出的元素是否属于
nums1。如果是，更新结果数组result相应位置的值为T[i]。 - 重复此过程直到栈空或当前元素不再大于栈顶元素。
- 弹出栈顶元素，因为已经找到其右边第一个更大的元素（即当前元素
- 描述：当
预处理代码如下：
while (!st.empty() && nums2[i] > nums2[st.top()]) {
if (umap.count(nums2[st.top()]) > 0) { // 检查是否在nums1中
int index = umap[nums2[st.top()]]; // 获取在nums1中的索引
result[index] = nums2[i]; // 更新结果数组
}
st.pop(); // 弹出栈顶元素
}
st.push(i); // 将当前索引入栈
以上分析完毕，完整C++代码如下：
// 版本一
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 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;
}
};
题目三：503.下一个更大元素II
503. 下一个更大元素 II
解题思路：
1. 直接拼接数组
- 将原数组复制并拼接到自身末尾，形成一个新的数组。
- 使用单调栈遍历新数组，找出每个元素后面第一个更大的元素。
- 将结果数组截取到原始大小。
2. 模拟循环遍历
- 不实际修改原数组，而是在遍历过程中模拟循环。
- 使用
i % nums.size()来模拟索引的循环，即当索引超出数组大小时从头开始。
==模拟索引的循环是一种在处理环形或循环数组问题时常用的技巧。==在某些问题中，我们需要处理数组的循环性质，即数组的末尾连接到数组的开头。这可以通过数学上的模运算（取余数）来实现。
代码如下：
// 版本一
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
// 拼接一个新的nums
vector<int> nums1(nums.begin(), nums.end());
nums.insert(nums.end(), nums1.begin(), nums1.end());
// 用新的nums大小来初始化result
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
// 开始单调栈
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < nums[st.top()]) st.push(i);
else if (nums[i] == nums[st.top()]) st.push(i);
else {
while (!st.empty() && nums[i] > nums[st.top()]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
}
// 最后再把结果集即result数组resize到原数组大小
result.resize(nums.size() / 2);
return result;
}
};
这种写法确实比较直观，但做了很多无用操作，例如修改了nums数组，而且最后还要把result数组resize回去。
resize倒是不费时间，是O(1)的操作，但扩充nums数组相当于多了一个O(n)的操作。
其实也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。
代码如下：
// 版本二
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size() * 2; i++) {
// 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());
else if (nums[i % nums.size()] == nums[st.top()]) st.push(i % nums.size());
else {
while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
result[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
}
return result;
}
};
可以版本二不仅代码精简了，也比版本一少做了无用功！
最后在给出 单调栈的精简版本，即三种情况都做了合并的操作。
// 版本二
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
stack<int> st;
for (int i = 0; i < nums.size() * 2; i++) {
// 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
result[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
return result;
}
};
总结
单调栈是一种特殊的栈结构，它在算法中用于处理与序列顺序相关的问题，尤其是那些需要找到序列中元素的后续或前置元素满足某种单调性条件的问题。
核心思想
- 利用栈来维护一个单调递增或递减的序列。
- 通过栈实现对数组元素的后续遍历，以找到满足特定条件的元素。
注意事项
- 确保栈内元素的顺序满足单调性要求。
- 在处理完所有元素后，检查栈中是否还有未处理的元素，这些元素后面没有更大的元素。
- 考虑边界条件，如数组的第一个元素或数组末尾的元素。
性能
- 单调栈通常能够在 O(n) 时间复杂度内解决问题，其中 n 是数组的长度。
- 空间复杂度通常为 O(n)，因为最坏情况下可能需要存储整个数组的索引。