算法训练营第50天|739. 每日温度|496.下一个更大元素 I|503.下一个更大元素II
739. 每日温度
1. 什么时候用单调栈呢？
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
是用一个栈来记录我们遍历过的元素
2.三种情况不同处理
情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
for(int i=1;i<temperatures.length;i++)
{
while (!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()])
{
int r = stack.pop();
result[r]=i-r;
}
stack.push(i);
}496.下一个更大元素 I
思路：这道题与上一道题类似，但是求的是值，所以堆栈里存的是遍历过的值。除此之外，需要一个map联系起两个数组。
503.下一个更大元素II
思路：遇到环时，要用线性去模拟。可以用取余的方法模拟环。
原文地址：https://blog.csdn.net/bless_______/article/details/140709212
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！