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

第四十八天打卡，坚持！今天学习了单调栈的知识和其能对应解决的问题

---

739.每日温度

题目链接

解题过程

• 采用单调栈的思路，通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用v单调栈了。
• 这里我们要使用递增循序（指从栈头到栈底的顺序，也就是栈顶是最小的元素），因为只有递增的时候，栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

单调栈

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int>result(temperatures.size());
        stack<int>st;
        st.push(0);
        for (int i = 1; i < temperatures.size(); i++) {
            while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
                result[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }
        return result;
    }
};

---

496.下一个更大元素Ⅰ

题目链接

解题过程

• 采用哈希表和单调栈，哈希表记录每个数后比自己更大的数是什么，单调栈负责采集数据

单调栈

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int>umap;
        stack<int>st;
        st.push(nums2[0]);
        for (int num : nums2) {
            while (!st.empty() && num > st.top()) {
                umap[st.top()] = num;
                st.pop();
            }
            st.push(num);
        }
        vector<int>result(nums1.size(), -1);
        for (int i = 0; i < result.size(); i++) {
            if (umap.find(nums1[i]) != umap.end()) {
                result[i] = umap[nums1[i]];
            }
        }
        return result;
    }
};

---

503.下一个更大元素Ⅱ

题目链接

解题过程

• 直接把两个数组拼接在一起，然后使用单调栈求下一个最大值，将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。
• 也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。

扩充数组+单调栈

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            nums.push_back(nums[i]);
        }
        vector<int>result(nums.size(), -1);
        stack<int>st;
        st.push(0);
        for (int i = 1; i < nums.size(); i++) {
            while (!st.empty() && nums[st.top()] < nums[i]) {
                result[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        result.resize(len);
        return result;
    }
};

不扩充数组+单调栈

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int len = nums.size();
        vector<int>result(len, -1);
        stack<int>st;
        st.push(0);
        for (int i = 1; i < 2 * len; i++) {
            while (!st.empty() && nums[i % len] > nums[st.top()]) {
                result[st.top()] = nums[i % len];
                st.pop();
            }
            st.push(i % len);
        }
        return result;
    }
};

原文地址：https://blog.csdn.net/qq_61552256/article/details/142849785

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！