当前位置：首页 > article >正文

代码随想录算法训练营第五十八天|739. 每日温度、496.下一个更大元素 I

article 2025/1/12 0:39:19

LeetCode 739 每日温度

题目链接：https://leetcode.cn/problems/daily-temperatures/

思路：

方法一:暴力解法

两个for循环，一个遍历数组，一个去找当前遍历数值的右边第一个比它大的值的下标

代码：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int>result;

        for(int i = 0; i < temperatures.size(); i++)
        {
            for(int j = i + 1; j < temperatures.size(); j++)
            {
                int index = 0;
                if(temperatures[j] > temperatures[i])
                {
                    index = j - i;
                    result.push_back(index);
                    break;
                }

                if(j== temperatures.size() - 1 && index ==0)
                    result.push_back(index);
            }
        }
        
        result.push_back(0);
        return result;
    }
};

方法二:单调栈

用空间换时间，相当于把第二个for循环用一个栈去替代了
什么时候用到单调栈？
答：寻找一个数右边（左边）比它大（小）的第一个数
单调栈的作用
答：可以把当前遍历的数的前面所有的数记录下来
具体过程
代码随想录

代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int>result(temperatures.size(), 0);
        stack<int>st;   // 单调栈
        st.push(0);

        for(int i = 1; i < temperatures.size(); i++)
        {
            if(temperatures[i] <= temperatures[st.top()])
                st.push(i);
            else
            {
                while(!st.empty() && temperatures[i] > temperatures[st.top()])
                {
                    result[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
        }

        return result;
    }
};

总结

开始学习单调栈的内容

LeetCode 496 下一个更大元素 I

题目链接：https://leetcode.cn/problems/next-greater-element-i/

思路：

方法一:暴力解法

三个for循环，一个遍历nums1数组，一个遍历nums2数组找到和当前nums1数组相同值的下标，最后一个循环是从找到相同值的下标+1开始往后找第一个比当前值大的值

代码：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int>result(nums1.size(), -1);

        for(int i = 0; i < nums1.size(); i++)
        {
            for(int j = 0; j < nums2.size(); j++)
            {
                if(nums1[i] == nums2[j])
                {
                    for(int tmp = j + 1; tmp < nums2.size(); tmp++)
                    {
                        if(nums2[tmp] > nums2[j])
                        {
                            result[i] = nums2[tmp];
                            break;
                        }
                    }
                }
            }
        }

        return result;
    }
};

方法二:单调栈

本题关键点：

result数组的大小
答：因为题目说了，nums1的数在nums2中均可以找到，所以显然result数组的大小为nums1.size()
要懂得如何在nums2数组中找出和nums1数组相同的值
答：题目中说了是两个没有重复元素的数组nums1和nums2。没有重复元素，我们就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。
单调栈的遍历是遍历哪个数组
答：因为是要在nums2中找比当前值更大的数，所以显然是遍历nums2数组

代码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int>map;
        vector<int>result(nums1.size(), -1);
        if(nums1.size() == 1)   return result;
        stack<int>st;
        st.push(0);

        // 将数组1的值和对应下标存进去map中，这样后续在nums2中用单调栈时有判断的条件
        for(int i = 0; i < nums1.size(); i++)
            map[nums1[i]] = i;

        // 因为要找的是数组2中对应元素右边更大的元素，所以遍历数组2
        for(int i = 1; i < nums2.size(); i++)
        {
            if(nums2[i] <= nums2[st.top()])
                st.push(i);
            else
            {
                while(!st.empty() && nums2[i] > nums2[st.top()])
                {
                	// 判断当前值是否是在数组1里的
                    if(map.find(nums2[st.top()]) != map.end())
                        result[map[nums2[st.top()]]] = nums2[i];
                    st.pop();
                }
                st.push(i);
            }
        }

        return result;
    }
};