北京网站建设的服务商,中国建设银行企业信息门户网站,那个网站可以做网站测速对比,宁波市建设教育培训网题目#xff1a; 给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替。
示例 1…题目 给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
示例 1: 输入: temperatures [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0] 示例 2: 输入: temperatures [30,40,50,60] 输出: [1,1,1,0] 示例 3: 输入: temperatures [30,60,90] 输出: [1,1,0] 思路 单调栈解决的问题是从左或者从右开始比这个元素大的或者小的第一个元素的问题 该题目的实现思路是创建一个单调栈使用存放单调递增的元素下标记住单调栈是存放的下标并不是元素 创建一个result数组并初始化为0后边会说为什么初始化为0 result数组用来存放每个元素相较于右边第一个比他大的元素的距离 具体实现过程 首先将第一个元素的下标入栈接下来在for循环中从第二个元素开始如果当前的元素小于等于栈顶的元素 那么需要将当前的元素下标入栈相反如果大于的话需要将当前栈顶的下标出栈并且将栈顶保存的下标对应到result数组中 并使用当前的下标i将去栈顶存的下标st.top()存放到result对应位置上最后再将栈顶元素出栈 出站后还需要继续判断当前元素和栈顶的关系如果还是大于那么继续执行刚刚的操作如果小于等于那么入栈 有可能会出现栈中还有元素但是T数组以及遍历完了这种情况栈中的元素全部是单调递增的后边没有比他更大得了 因此就用到了初始化的result数组为0了。 class Solution {
public:vectorint maxlength(vectorint T) {stackint st;vectorint 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;}
};int main() {vectorint temperatures { 73, 74, 75, 71, 69, 72, 76, 73 };Solution ss;vectorint result ss.maxlength(temperatures);for (vectorint::iterator pos result.begin(); pos ! result.end();pos) {cout *pos ;}return 0;
}
