LeetCode 739每日温度 496 下一个更大元素 | 代码随想录25期训练营day58

单调栈1

LeetCode 739 每日温度 2023.12.21

• 题目链接
• 代码随想录讲解[链接]
  

vector<int> dailyTemperatures(vector<int>& temperatures) {
    //暴力求解，但会超时
    /*
        vector<int> answer(temperatures.size(), 0);
        for (int i = 0; i < temperatures.size(); i++)
        {
            for(int j = i+1; j < temperatures.size(); j++)
            {
                if(temperatures[j] > temperatures[i])
                {
                    answer[i] = j - i;
                    break;
                }
            }
        }
        return answer;
        */

    //单调栈求解
    //answer数组存储题目答案
    vector<int> answer(temperatures.size(), 0);
    //创建单调栈存储已经遍历过的元素的索引，且该栈元素呈单调递增
    stack<int> st;
    //正序遍历
    for (int i = 0; i < temperatures.size(); i++)
    {
        //当栈不为空且栈顶索引的温度小于当前遍历温度时
        //这里是循环，不是if
        while(!st.empty() && temperatures[st.top()] < temperatures[i])
        {
            //存储答案
            answer[st.top()] = i - st.top();
            //有答案的索引被去掉
            st.pop();
        }
        //这里的条件是走完了上面的循环或者索引的温度大于或等于当前遍历温度
        st.push(i);
    }
    return answer;
}

LeetCode 496 下一个更大元素 2023.12.21

• 题目链接
• 代码随想录讲解[链接]
  

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    //暴力搜索
    /*
        vector<int> ans(nums1.size(), -1);
        for (int i = 0; i < nums1.size(); i++)
        {
            //找到nums1[i]在nums2中的索引
            int pos = find(nums2.begin(), nums2.end(), nums1[i]) - nums2.begin();
            for(int j = pos + 1; j < nums2.size(); j++)
            {
                if(nums2[j] > nums1[i])
                {
                    ans[i] = nums2[j];
                    break;
                }
            }
        }
        return ans;
        */

    //单调栈
    //ans数组存储题目答案,默认值设为-1，因为找不到的话是-1
    vector<int> ans(nums1.size(), -1);
    //创建单调栈存储已经遍历过的元素的索引，且该栈元素呈单调递增
    stack<int> st;
    //因为nums1是nums2的子集，而且搜索的是nums2数组，所以遍历nums2数组
    for (int i = 0; i < nums2.size(); i++)
    {
        //当栈不为空且栈顶索引的数值小于当前遍历数值时
        //这里是循环，不是if
        while (!st.empty() && nums2[i] > nums2[st.top()])
        {
            //这里查找栈顶索引对应的元素是否为nums1中元素，如果是，则记录进ans中
            vector<int>::iterator it = find(nums1.begin(), nums1.end(), nums2[st.top()]);
            if(it != nums1.end())
                ans[it-nums1.begin()] = nums2[i];
            //删除栈顶元素
            st.pop();
        }
        //这里的条件是走完了上面的循环或者索引的数值大于或等于当前遍历数值
        st.push(i);
    }
    return ans;
}