单调栈，主要用于记录数组中每个元素的下一个更大值。
为了在O（n）时间复杂度内完成这个目标，需要从后往前维护一个单调递增栈，栈中依次存储当前下一个位置到数组尾的下一个更大值。因此，对于每个位置的更新，只需要从栈中将小值出栈，直到寻找到比当前值大的值即可。
话不多说直接看题
1019. Next Greater Node In Linked List
题意：
给定一个链表， 对于每个节点，记录链表中下一个比当前节点大的节点值，最终结果用数组返回。
思路：
寻找下一个更大节点问题，典型的单调栈问题，首先将链表转化为数组即可直接套单调栈模板
代码：
/*
Author Owen_Q
*/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
int n = 0;
vector<int> a;
while(head!=NULL)
{
a.push_back(head->val);
n++;
head = head->next;
}
vector<int> re(n);
stack<int> st;
for(int i=n-1;i>=0;i--)
{
while((!st.empty())&&a[i] >= st.top())
{
st.pop();
}
if(st.empty())
re[i] = 0;
else
re[i] = st.top();
st.push(a[i]);
}
return re;
}
};
496. Next Greater Element I
题意：
在数组2中寻找数组1中相应值的下一个更大元素
思路：
依旧是单调栈问题，只是多了一个数组，那么只需要对数组2进行单调栈维护，并对结果进行hash映射，然后在数组1中进行查找。
代码：
/*
Author Owen_Q
*/
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack <int> st;
int n = nums2.size();
vector<int> re(1e5+7,-1);
for(int i=n-1;i>=0;i--)
{
while((!st.empty())&&nums2[i] >= st.top())
{
st.pop();
}
if(!st.empty())
re[nums2[i]] = st.top();
st.push(nums2[i]);
}
vector<int> re1;
for(int i:nums1)
re1.push_back(re[i]);
return re1;
}
};
503. Next Greater Element II
题意：
循环版下一个更大元素，数组成为了循环数组
思路：
只需要维护两轮单调栈即可
代码：
/*
Author Owen_Q
*/
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
stack <int> st;
vector<int> re(n);
for(int i=n-1;i>=0;i--)
{
while((!st.empty())&&nums[i] >= st.top())
st.pop();
if(st.empty())
re[i] = -1;
else
re[i] = st.top();
st.push(nums[i]);
}
for(int i=n-1;i>=0;i--)
{
while((!st.empty())&&nums[i] >= st.top())
st.pop();
if(st.empty())
re[i] = -1;
else
re[i] = st.top();
st.push(nums[i]);
}
return re;
}
};
739. Daily Temperatures
题意：
记录每天温度距离下一次更高温度所相隔的天数
思路：
这次记录的不是更大值，而是更大值所在的问题，因此将单调栈中维护的元素从值本身改为位置坐标即可
代码：
/*
Author Owen_Q
*/
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack <int> st;
int n = T.size();
vector<int> re(n);
for(int i=n-1;i>=0;i--)
{
while((!st.empty())&&T[i] >= T[st.top()])
st.pop();
if(st.empty())
re[i] = 0;
else
re[i] = st.top() - i;
st.push(i);
}
return re;
}
};
此外，对于单调栈的更复杂的运用，感兴趣的朋友可以去体验一下阿里的一道题：
最大01子矩阵问题（单调栈优化）
