「代码随想录算法训练营」第四十一天 | 单调栈 part1

739. 每日温度

题目链接:https://leetcode.cn/problems/daily-temperatures/
文章讲解:https://programmercarl.com/0739.每日温度.html
题目难度:中等
视频讲解:https://www.bilibili.com/video/BV1my4y1Z7jj/
题目状态:看题解

思路:

定义一个单调栈,该栈存放下标,规则是要保持其下标对应的温度值从栈底到栈头是单调递减的。再定义一个和题目数组大小相等的数组ans存放结果,初始化为0。具体步骤如下:

  1. 先将第一个元素的下标存入栈中。
  2. 循环遍历温度数组:
    • 若当前温度小于等于栈头元素的温度,将当前温度的下标压入栈。
    • 若当前温度大于栈头元素的温度,将栈中比当前温度低的元素都弹出,在弹出的时候将其压入结果数组中(i-st.top()),直到栈头大于当前温度,将当前温度的下标压入栈。
  3. 遍历结束后,返回结果数组。

代码:

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

496. 下一个更大元素 I

题目链接:https://leetcode.cn/problems/next-greater-element-i/
文章讲解:https://programmercarl.com/0496.下一个更大元素I.html
题目难度:简单
视频讲解:https://www.bilibili.com/video/BV1jA411m7dX/
题目状态:用其他方法过的,看题解学习一下单调栈的方法

思路一:嵌套循环

非常传统的方法,遍历整个nums1,每遍历一个元素就在nums2中找到对应的元素下标,然后再在nums2中从下标位置开始向后遍历,直到找到一个比元素大的元素,将其值填入结果数组中并跳出循环,若找不到直接返回,因为这个结果数组初始化的时候将其全部值初始化为-1了。

代码一:

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size();
        vector<int> ans(len1, -1);
        for(int i = 0; i < len1; ++i) {
            auto it = find(nums2.begin(), nums2.end(), nums1[i]);
            int index = distance(nums2.begin(), it);
            for(int j = index; j < len2; ++j) {
                if(nums2[j] > nums1[i]) {
                    ans[i] = nums2[j];
                    break;
                }
            }
        }
        return ans;
    }
};

消耗:

思路二:单调栈

nums1压入一个unordered_map<int, int>中,主要原因是它的查询和增删效率是最优的。
然后维护一个单调栈st,这个栈从栈底到栈头是单调递减的,用来遍历nums2,当遇到元素比栈头元素大的时候,就判断一下栈头元素是否在nums1中存在,如果存在就表示其后面有比栈头元素高的元素,将这个元素值更新到结果数组中。

代码二:

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size();
        stack<int> st;
        vector<int> ans(len1, -1);
        if(len1 == 0) return ans;
        unordered_map<int, int> umap;
        for(int i = 0; i < len1; ++i) {
            umap[nums1[i]] = i; // key:下标元素,value:下标
        }
        // 将nums2压入单调栈
        st.push(0);
        for(int i = 1; i < len2; ++i) {
            if(nums2[i] <= nums2[st.top()]) st.push(i);
            else {
                while(!st.empty() && nums2[i] > nums2[st.top()]) {
                    if(umap.count(nums2[st.top()]) > 0) { // 看看umap中是否存在该元素
                        int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()]在nums1中的下标
                        ans[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return ans;
    }
};

消耗:

503. 下一个更大元素 II

题目链接:https://leetcode.cn/problems/next-greater-element-ii/
文章讲解:https://programmercarl.com/0503.下一个更大元素II.html
题目难度:中等
视频讲解:https://www.bilibili.com/video/BV15y4y1o7Dw/
题目状态:自己的思路没通过,好奇怪,chatGPT帮忙修改了一下,直接把我思路改了

思路:

  1. 循环数组处理

    • 为了模拟循环数组,我们遍历数组两次。这样可以确保每个元素都能找到它的下一个更大元素,即使这个元素在数组的末尾。
  2. 使用栈

    • 栈用来存储索引,而不是元素值。这使我们能够直接在结果数组中更新对应位置的值。
  3. 遍历数组

    • 在每次遍历中,我们检查当前元素是否大于栈顶元素对应的值。
    • 如果是,则更新结果数组中栈顶元素索引对应的值,并弹出栈顶。
    • 如果当前索引在数组的前半部分(即小于 len),我们将其索引压入栈中。
  4. 结果更新

    • 通过这种方式,所有元素的下一个更大元素都会在结果数组中被正确更新。

代码:

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

消耗: