下一个更大元素

今天解题遇到了一个类型的题目，都是使用单调栈来进行求解，感觉可以记录一下。

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] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

答：使用单调栈优先处理nums2，从后往前进行，如果栈为空说明找不到更大元素，设置为-1，并把自身压入单调栈中。如果栈不为空则比较自身与栈顶大小，栈顶小则一直pop()直到自身比栈顶小或者栈为空，如果自身比栈顶小则说明栈顶元素为更大元素。在解决的途中使用哈希表unordered_map进行存储更大元素，键：nums2的值，值：对应的更大元素的值。这样遍历nums1的同时可以根据哈希表的对应关系直接找到对应元素的更大元素。

public:

    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {

        unordered_map<int,int> hashmap;

        stack<int> stk;

        vector<int> res(nums1.size());

        for(int i=nums2.size()-1;i>=0;i--)

        {

            int m = nums2[i];

            while(!stk.empty()&&m>=stk.top())

            {

                stk.pop();

            }

            hashmap[m]=stk.empty()?-1:stk.top();

            stk.push(m);

        }

        for(int i=0;i<nums1.size();i++)

        {

            res[i]=hashmap[nums1[i]];

        }

        return res;

    }

};

下一个更大元素Ⅱ

给定一个循环数组 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 <= 104
-109 <= nums[i] <= 109

答：这道题目一样是使用单调栈进行求解，区别在于这道题目的数组设定为一个循环数组，所以一次循环并不能完美解决问题，所以需要循环两次，亦或者类同于把数组延长为2*n-1大小，把最后一位前面部分再后移也能解决问题。关键在于使用%来获取余数。

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

};