LeetCode 739 每日温度

题目： 给定一个整数数组 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:vector<int> maxlength(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 {while (!st.empty()&& T[i] > T[st.top()]) {result[st.top()] = i - st.top();st.pop();}st.push(i);}}return result;}
};int main() {vector<int> temperatures = { 73, 74, 75, 71, 69, 72, 76, 73 };Solution ss;vector<int> result= ss.maxlength(temperatures);for (vector<int>::iterator pos = result.begin(); pos != result.end();pos++) {cout << *pos <<" ";}return 0;
}