代码随想录算法训练营第41天 | 第九章动态规划 part14

第十章 单调栈 part01

739. 每日温度

今天正式开始学习单调栈，这是单调栈的一道扫盲题目，同时也是一道经典题。

大家可以先读题，思考暴力解法，然后再看单调栈的解法。通过对比这两种解法，可以更好地感受到单调栈的巧妙之处。

点击查看题解

单调栈用来存储数组下标。
使用单调栈主要有三个判断条件。

当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

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

没想到单调栈不难，挺简单的。不建议看文字，直接看代码随想录的视频。豁然开朗，直接势如破竹，秒杀。单调栈用来存下标，然后来了新的，判断下是否更大，更大就把小的滚，通过下标差确定大小。一直欺负弱小。要是小了，就老老实实呆在栈里。

---

496. 下一个更大元素 I

这道题看似和 739. 每日温度 类似，但实际上增加了一些难度。实际上并不难，主要是多了一个哈希表，通过 unordered_map，可以快速查找 nums1 中元素对应的下标，方便在之后的操作中将结果存储到正确的位置。

点击查看题解

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> umap; //定义一个哈希表
for (int i = 0; i < nums1.size(); i++) {
    umap[nums1[i]] = i;
}
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        for(int i=0;i<nums2.size();i++)
        {
            while(st.empty()!=1&&nums2[i]>nums2[st.top()])
            {
               if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
                    int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
                    result[index] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }
        return result;
    }
};

---

503. 下一个更大元素 II

这道题与 739. 每日温度 几乎如出一辙，大家可以尝试独立完成。
将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。确实好聪明。我想到的方法是，找到最大的值index，然后向右移nums.size()-index.
其实也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。代码确实挺妙呢。

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

而是在遍历的过程中模拟走了两边nums。

点击查看题解

原文地址：https://blog.csdn.net/zxjiaya/article/details/142924335

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