代码随想录算法训练营day58||739. 每日温度 ||496.下一个更大元素 I ||503.下一个更大元素II

739. 每日温度

题目描述：

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

思路：

1.这道题首先可以想到的就是暴力解法，两层for循环就可以求出

2.使用单调栈的方法：

怎么想到使用单调栈？什么时候用单调栈？

 通常是一维数组，要寻找任意元素的左边或者右边第一个比自己大或者比自己小的元素的位置，此时我们就可以想到使用单调栈。

单调栈的原理是什么？为什么o(n)的时间复杂度就可以找到每一个元素的右边第一个比他大的元素位置呢？

单调栈的本质就是空间换时间，因为遍历过程中需要一个栈来记录右边第一个比当前元素高的元素，优点是只用遍历一次。

使用单调栈的时候明确如下几点：

1.单调栈里存放的元素是什么？

单调栈里只需要存放元素的下标i就可以，如果需要使用对应的元素，直接T[i]就可以获取。

2.单调栈里元素是递增呢？还是递减？

注意一下顺序是从栈顶到栈底：

这里使用的是递增顺序，只有递增的顺序，加入一个元素i，才知道是栈顶元素在数组中右边比栈顶元素大的是i.

单调栈主要有三个判断条件：

T[i]

T[i]==T[st.top()]

T[i]>T[st.top()]

class Solution {
public:
    vector<int> dailyTemperatures(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 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;
    }
};

496.下一个更大元素 I

思路：

大致思路与上一题一样但是比上一题更绕一些，首先我们创建一个result的数组的大小与nums1的大小相同，全部初始化为-1，默认没有找到更大元素，如果后面找到了就进行操作，如果没找到就保持-1，然后我们还是用单调栈的方法遍历nums2数组，同样是三种情况，nums[i]nums[st.top()],

前两种情况进行压栈操作，最后一种情况，进行判断，nums2[st.top()]元素是否在nums1中出现过，如何判断有没有出现过，我们用一个unordered_map容器存下，nums1中的元素和下标，判断nums2[st.top()]中元素是否出现在nums1过用if(umap.count(nums2[st.top()]))判断，如果大于0就出现过，相应的result数组的位置上进行赋值。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        if (nums1.size() == 0) return result;
 
        unordered_map<int, int> umap; // key:下标元素，value：下标
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        st.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            if (nums2[i] < nums2[st.top()]) {           // 情况一
                st.push(i);
            } else if (nums2[i] == nums2[st.top()]) {   // 情况二
                st.push(i);
            } else {                                    // 情况三
                while (!st.empty() && nums2[i] > nums2[st.top()]) {
                    if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
                        int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
                        result[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

503.下一个更大元素II

思路：

与第一题不同的是这是一个循环数组，其实解决这题，我们可以想到将数组遍历两次就可以了，

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        //下一个元素更大，要进行走俩趟，
    vector<int> result(nums.size(),-1);
    stack<int> st;
    st.push(0);
    for(int j=0;j<2;j++)
    for(int i=0;isize();i++){
        if(nums[i]<=nums[st.top()]){
            if(i!=0) st.push(i);
        }else{
            while(!st.empty()&&nums[i]>nums[st.top()]){
                result[st.top()]=nums[i];
                st.pop();
            }
            st.push(i);
        }
    }
    return result;
    }
};