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

739.每日温度

文字讲解：代码随想录

视频讲解：单调栈，你该了解的，这里都讲了！LeetCode:739.每日温度_哔哩哔哩_bilibili

解题思路

思路一：暴力双循环

O（n^2）

思路二：单调栈（用来找到右边或者左边第一个比它大的元素）

元素：利用一个栈来存下标i，用T[i]来做映射

顺序（递增还是递减）：如果是递增是求左边或者右边第一个比它大的元素

否则就是求比它小的元素

作用：用一个单调栈来记录我们遍历过哪些元素

使用：用当前元素和栈口元素进行比较

T[i] > T[st.top()]

此时找到了第一个比它大的元素 记录结果result[st.top()] 结果下标一定是栈顶元素下标

因为结果已经记录了，栈顶元素就没用了，直接弹出st.pop()，并push(i)

T[i] < T[st.top()] 

那么就加入到栈中，这样从栈口到栈顶就是单调递增的

T[i] == T[st.top()]

也加入到栈中

过程模拟

首先先将第一个遍历元素加入单调栈

加入T[1] = 74，因为T[1] > T[0]（当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况）。

我们要保持一个递增单调栈（从栈头到栈底），所以将T[0]弹出，T[1]加入，此时result数组可以记录了，result[0] = 1，即T[0]右面第一个比T[0]大的元素是T[1]。

加入T[2]，同理，T[1]弹出

加入T[3]，T[3] < T[2] （当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况），加T[3]加入单调栈。

这样就不难看出为什么result要使用栈顶元素下标，以及递增单调栈的处理过程和比较过程

如果元素遍历完后一直在栈里，那就是默认为0，没有找到比他大的情况

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> result(temperatures.size(),0);
        if(temperatures.size()==1) return result;
        st.push(0);     //放入第一个遍历的元素
        for(int i = 1 ;i < temperatures.size() ; i++)
        {
              if(temperatures[i]<temperatures[st.top()])  //小于当前栈顶元素
              st.push(i);
              else 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

文字讲解：代码随想录

视频讲解：单调栈，套上一个壳子就有点绕了| LeetCode:496.下一个更大元素_哔哩哔哩_bilibili

解题思路

1.先定义一个result数组，大小是nums1的大小，默认为-1

2.单调栈遍历的是num2，我们要在哪里找比他大的元素的，就在哪里用单调栈遍历

3.建立nums1和nums2的关系，用哈希来建立映射，nums2中的元素是否在nums1中出现过，如果出现过，要找到nums1中对应的下标

4.本题要找第一个大的，因此用递增栈

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
            stack<int> st;
            vector<int> result(nums1.size(),-1);
            if(nums1.size()==0) return result;
            unordered_map<int,int> map;
            for(int i = 0 ;i < nums1.size() ;i++) map[ nums1[i] ] = i ;   //用元素的数值去找到在nums1中对应的下标
            //num1和num2和桥梁是元素的值，因此作为key
            st.push(0);
            for(int i = 0 ;i < nums2.size(); i++)
            {
                if(nums2[i] < nums2[st.top()] || nums2[i]==nums2[st.top()])
                 st.push(i);
                else
                {
                    while(!st.empty() && nums2[i]>nums2[st.top()])
                    {
                            if( map.find(nums2[st.top()])!= map.end() )   //栈顶元素是nums1中的数
                            {
                                    int index = map[ nums2[ st.top() ] ];
                                    result[ index ] = nums2[i];
                            }
                            st.pop();
                                
                    }
                    st.push(i);
                }
            }
            return result;
    }
};

503.下一个更大元素II

文字讲解：代码随想录

视频讲解：单调栈，成环了可怎么办？LeetCode：503.下一个更大元素II_哔哩哔哩_bilibili

解题思路：

本题是环形

思路一：再开辟一个一样的数组，拼接起来，然后用新数组做一个单调栈，最后取前三个值

思路二：环形或者首尾相连的通法就是取模

for(int i = 0 ; i < nums.size() * 2 ; i ++)

                i % nums.size()

剩下的就是模版了

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
            vector<int> result(nums.size(),-1);
            stack<int> st;
            st.push(0);
            for(int i = 1 ; i<nums.size()*2; i++)
            {
                 if(nums[i % nums.size()]<nums[st.top()] || nums[i % nums.size()]==nums[st.top()])
                 st.push(i % nums.size());   //小于等于，就加入单调
                 else
                 {
                    while(!st.empty() && nums[st.top()] < nums[i % nums.size()])
                    {
                        result[st.top()] = nums[i % nums.size()];
                        st.pop();
                    }
                    st.push(i % nums.size());
                 }
            }
            return result;
    }
};

常见疑惑

循环判断两遍后，是否会被覆盖？

并不会

例如 432432

结果 -1 4 4 -1 -1 -1

到第二次4之后的23都是在栈里的

此时栈是234，因此不会覆盖

例如234234

结果 3 4 -1 3 4 -1

此时从最后一个4更新第一遍的3的结果后，栈就不会更新元素了

此时栈是 4 3 2 4