算法刷题记录 Day50

算法刷题记录 Day50

Date: 2024.04.18

lc 739. 每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> next(temperatures.size(), 0);
        // 我们希望找到下一个更大值;
        // 使用一个栈来保存序号。每次遇到一个新元素，判断之前的元素是否比当前元素小。小则退栈，并记录下一个更大值。
        stack<int> st;
        int cur_idx = 0;
        while(cur_idx < temperatures.size()){
            while(!st.empty() && temperatures[cur_idx] > temperatures[st.top()]){
                next[st.top()] = cur_idx - st.top();
                st.pop();
            }
            st.push(cur_idx);
            cur_idx++;
        }
        return next;
    }
};

lc 496. 下一个更大元素I

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

        int cur_idx = 0;
        stack<int> st;
        // nums1 是 nums2的子集。因此，思路一：使用一个哈希表记录nums1中单词。然后遍历nums2，单调栈。
        unordered_map<int, int> dict;   //(value, nums1中idx)；
        for(int i=0; i<nums1.size(); i++){
            dict.insert({nums1[i], i});
        }

        while(cur_idx < nums2.size()){
            while(!st.empty() && nums2[cur_idx] > nums2[st.top()]){
                int pop_idx = st.top();
                st.pop();
                if(dict.find(nums2[pop_idx]) != dict.end()){
                    next[dict[nums2[pop_idx]]] = nums2[cur_idx];
                }
            }
            st.push(cur_idx);
            cur_idx++;
        }
        return next;
    }
};