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

代码随想录打卡Day48

article 2024/10/2 11:18:36

今天是单调栈的第一天，用暴力遍历都能做，但是为了了解单调栈的思路，第一道题还是看了下视频，第三道题主要看了下怎么解决成环的问题，第二道题我甚至都没用到单调栈哈哈哈哈O(∩_∩)O明天就是国庆假期了，5天没有刷题任务哈哈哈哈哈

739. 每日温度

这道题需要返回一个整形向量，所以我们需要定义一个向量result，初始值全为0。另外再定义一个存放整形变量的栈，因为我们需要向result数组内填入两天的时间之差，所以我们必须在栈中保存元素的下标值，而不是元素本身。首先对栈进行初始化，将数组中的第一个元素的下标压入栈中，也就是0，然后用一个for循环遍历整个数组，如果遍历到的元素是小于等于当前栈顶元素的，就将当前遍历的元素下标也压入栈中，确保从栈顶到栈底，元素是单调递增的。如果遍历到的元素大于当前栈顶元素，则用一个while循环持续地将栈内小于当前遍历值的元素下标弹出，并将i - st.top()写入result[st.top()]，当栈为空或者栈顶元素大于等于当前遍历值时循环终止，在循环终止后将当前遍历值的下标压入栈中。循环结束后栈内还有元素不要紧，说明这些元素的右边已经找不到更大的值了，result数组对应的位置上应该填0，但是之前定义result数组时已经定义为全0数组了，所以这里就不需要考虑了。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> result(temperatures.size(), 0);
        //初始化，将第一个元素下标压入栈中
        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;
    }
};

496.下一个更大元素 I

这道题自己写的，自己写的时候甚至都没有用到栈，没有用单调栈的思路去做，但是空间复杂度还行，我就没去看视频讲解了。
这道题我直接用两层for循环来做的，外层for循环来遍历nums1中的元素，然后内层循环用来寻找nums2中对应元素的右边是否有更大值，主要通过find函数来实现，内层循环首先找到该元素在nums2中的位置，然后迭代器持续地向数组末端移动，如果找到了比当前元素更大的值，则直接将该值填入result数组中的对应位置，如果没有找到，就什么都不做。

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(auto it = find(nums2.begin(), nums2.end(), nums1[i]); it != nums2.end(); it++){
                if(*it > nums1[i]){
                    result[i] = *it;
                    break;
                }
            }
        }
        return result;
    }
};

503.下一个更大元素II

这道题和第一道题比较像，但是这道题和第一题的不同之处在于，这道题的数组是环形结构，这道题要求填入的是元素值而不是元素下标之差，为了解决环形结构问题，这道题我们首先需要遍历两倍nums.size()次，使得数组能够首尾相连，但是每次遍历的元素并不是nums[i],而是nums[i % nums.size()]，这样就能保证在遍历完nums[nums.size() - 1]后可以再次从下标为0的元素开始遍历，这样整个result数组实际上会被赋值2遍，但是在同一位置的两次赋值操作都是完全相同的，所以不必担心遍历两边之后原来正确的值被赋值成错的。其他地方和第一题都是一样的。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        int m = nums.size();
        vector<int> result(m, -1);
        //初始化，将第一个元素的下标压入栈中
        st.push(0);
        for(int i = 1; i < m * 2; i++){  //首尾相接，相当于拼接成原来长度两倍的数组
            if(nums[i % m] <= nums[st.top()]) //当前遍历到的元素小于等于栈顶元素，需要入栈
                st.push(i % m);
            else{
                while(!st.empty() && nums[st.top()] < nums[i % m]){
                    result[st.top()] = nums[i % m];
                    st.pop();
                }
                st.push(i % m);
            }
        }
        return result;
    }
};