leetcode_day50

今日内容：

• 739. 每日温度 medium
• 496.下一个更大元素 I easy
• 503.下一个更大元素II medium

739. 每日温度

题目：

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1: 输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

思路：

首次思路

既然是单调栈专题，之前遇到过单调栈，但只有模糊的认识：单调栈就是有一个特殊入栈出栈规则的栈，这个规则构成了单调。

于是“照虎画猫”，开一个栈，使其从栈底到栈顶非递减，即：
- 元素比栈顶小或相等，入栈 - 元素比栈顶大，不断出栈直至比栈顶小或空

遍历到最后栈内的都是没有升高的，在初始化时就置零，之后就不用管了直接返回。

写的时候就能悟到，栈里面存下标要方便得多，于是写出下面的代码

carl思路

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

• 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况:入栈
• 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况：入栈
• 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况：不断出栈到不大于或空

栈内存下标。

代码

自己的-每日温度

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

carl的-每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        // 递增栈
        stack<int> st;
        vector<int> result(T.size(), 0);
        st.push(0);
        for (int i = 1; i < T.size(); i++) {
            if (T[i] < T[st.top()]) {                       // 情况一
                st.push(i);
            } else if (T[i] == T[st.top()]) {               // 情况二
                st.push(i);
            } else {
                while (!st.empty() && T[i] > T[st.top()]) { // 情况三
                    result[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

496.下一个更大元素 I

题目：

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2： 输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
提示：
- \(1 <= nums1.length <= nums2.length <= 1000\)
- \(0 <= nums1[i], nums2[i] <= 10^4\)
- nums1和nums2中所有整数 互不相同
- nums1 中的所有整数同样出现在 nums2 中

思路：

首次思路

俩for循环暴力搜索，我自己用单调栈好像也没优化到哪里去……

carl的思路

用map记忆化遍历，再遍历nums2，这样就不用在外面套一层nums1

代码

自己的-下一个最大元素I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans(nums1.size(), -1);
        
        for(int i = 0;i < nums1.size();i++) {
            int next = -1;//还没找到，先设置-1
            for(int j = 0;j < nums2.size();j++) {
                if(nums2[j] == nums1[i]) {
                    next = nums2[j];//找到了，开始找大
                }
                else if(next == -1) continue;//没找到继续找
                else if(nums2[j] > next) {
                    ans[i] = nums2[j];
                    break;
                }
            }
        }
        return ans;
    }
};

carl的-下一个最大元素I

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> umap; // key:下标元素，value：下标
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        st.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            while (!st.empty() && 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

题目：

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
提示:
\(1 <= nums.length <= 10^4\)
\(-10^9 <= nums[i] <= 10^9\)
## 思路： ### 我的思路

循环走就行，栈底的肯定最先被再次访问到，如果再次访问到栈底，那就退出，但是栈底还得用一次来挤出靠后的小元素，所以出循环得放在处理元素的后面。

既然要访问栈底，那用deque模拟栈。剩下的和之前如出一辙。

运行下来好像我的更快一点点，吼吼吼。 ### carl的思路

妙哉，把nums倍增一段，就算循环了，可以物理上直接倍增nums，也可以循环的时候把for的次数改成nums.size()*2，下标取模算法倍增。

代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> ans(nums.size(), -1);
        int i = 0, n = nums.size();
        deque<int> dq;
        while(true) {
            while(!dq.empty() && nums[dq.back()] < nums[i]) {
                ans[dq.back()] = nums[i];
                dq.pop_back();
            }
            if(!dq.empty() && i == dq.front()) break;//不能放while开头，会少处理
            if(ans[i] == -1) dq.push_back(i);
            i = (i+1) % n;
        }
        return ans;
    }
};

carl的

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;
        stack<int> st;
        for (int i = 0; i < nums.size() * 2; i++) {
            // 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
            while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }
        return result;
    }
};