算法随想Day51【单调栈】| LC739-每日温度、LC496-下一个更大元素Ⅰ

LC739. 每日温度

vector<int> dailyTemperatures(vector<int>& temperatures)
{
    int size = temperatures.size();
    vector<int> result(size, 0);
    vector<int> sta;
    sta.push_back(0);
    for (int i = 1; i < size; ++i)
    {   
        while (sta.empty() != true)
        {
            int temp = sta.back();
            if (temperatures[i] > temperatures[temp])
            {
                result[temp] = i - temp;
                sta.pop_back();
            }
            else
                break;
        }
        sta.push_back(i);
    }
    return result;
}

LC496. 下一个更大元素Ⅰ

使用一个unordered_map哈希表对nums1做映射（key：下标元素，value：下标）

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2)
{
    int size = nums1.size();
    vector<int> result(size, -1);
    vector<int> sta;
    sta.push_back(nums2[0]);
    unordered_map<int, int> umap;
    for (int i = 0; i < size; ++i)
    {
        umap[nums1[i]] = i;
    }
    for (int i = 1; i < nums2.size(); ++i)
    {
        if (nums2[i] > sta.back())
        {
            while (sta.empty() != true && nums2[i] > sta.back())
            {
                int temp = sta.back();
                if (umap.find(temp) != umap.end())
                {
                    result[umap[temp]] = nums2[i];
                }
                sta.pop_back();
            }
        }
        sta.push_back(nums2[i]);
    }
    return result;
}