具体来说我们什么时候选择考虑单调栈呢，答案是，通常是一位数组需要寻找一个元素的左边或者右边比自己大或者小的第一个元素的位置。
单调栈中的元素存的是元素的位置。
直白的来说，单调栈使用栈来记录一遍我们遍历过的元素的位置，一旦遍历元素的值大于栈顶的值，则栈顶元素右边比自己大的第一个元素的位置就是遍历元素的位置，然后栈顶元素需要出栈。
至于为什么叫单调栈，因为栈顶到栈底是有序的，如果是找一个元素右边第一个更大元素，则栈顶到栈底的顺序为递增。
每日温度
给定一个整数数组temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
class Solution {
public:
vector dailyTemperatures(vector& temperatures) {
int m = temperatures.size();
stack st;
vector result(m, 0);
st.push(0);
for(int i=0; i temperatures[st.top()]){
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return result;
}
}; 下一个更大元素 I
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是nums2的子集
- 2 对应位置 – 哈希表
- 3 更大元素 – 单调栈
求解方法：
- 1 首先我们先求出nums2数组的下一个更大元素数组。
- 2 其次建立一个nums1中元素-索引的哈希表{“元素”：索引}。
- 3 遍历nums2，找到nums1中元素的索引位置。
哈希表也可以继续使用nums2构建，都可以。
class Solution {
public:
vector nextGreaterElement(vector& nums1, vector& nums2) {
unordered_map<int, int> map;
stack st;
int m = nums1.size(), n = nums2.size();
vector result(m, -1);
vector vec(n, -1);
// 1 求解nums2的更大元素数组
st.push(0);
for(int i=1; i<n; i++){ while(!st.empty() && nums2[i] > nums2[st.top()]){
vec[st.top()] = nums2[i];
st.pop();
}
st.push(i);
}
// 2 使用nums1的值和索引构建哈希表
for(int i=0; i<m; i++){
map[nums1[i]] = i;
}
// 3 nums2的值去map中查询得到nums1的索引
for(int i=0; i<n; i++){
if (map.count(nums2[i])) result[map[nums2[i]]] = vec[i];
}
return result;
}
};
下一个更大元素 II
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
在上一题的基础上，数组变成循环数组。
最简单的做法就是将nums拼接，然后找下一个更大元素。最后删除多余的数组。
class Solution {
public:
vector find_next_element(vector& nums)
{
vector result(nums.size(), -1);
stack st;
st.push(0);
for(int i=1; i<nums.size(); i++) { while(!st.empty() && nums[i] > nums[st.top()])
{
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
return result;
}
vector nextGreaterElements(vector& nums) {
vector result;
vector new_nums;
for(int i=0; i<2*nums.size(); i++)
{
new_nums.push_back(nums[i%nums.size()]);
}
result = find_next_element(new_nums);
for(int i=0; i<nums.size(); i++)
{
result.pop_back();
}
return result;
}
};
class Solution {
public:
vector build_stack(vector& nums)
{
stack st;
vector result(nums.size(), -1);
st.push(0);
int j;
for(int i=1; i< 2*nums.size(); i++)
{
j = i % nums.size();
while(!st.empty() && nums[j] > nums[st.top()])
{
result[st.top()] = nums[j];
st.pop();
}
st.push(j);
}
return result;
}
vector nextGreaterElements(vector& nums) {
int m = nums.size();
vector result;
result = build_stack(nums);
return result;
}
};