496. 下一个更大元素 I

image-20211026095137887

解题思路：

​ 这题通过暴力法的话时间复杂度为O(nums1.length*nums2.length)。

​ 但是能引出一种时间复杂度为O(nums1.length+nums2.length)的思路，即单调栈+哈希表的方法。

​ 整体思路(s为栈,m为哈希表,res为结果向量)：

  1. 反向遍历nums2，每次遍历时在栈中令s.top()和nums2[i]进行比较，排出栈中所有比nums2[i]小的元素，将栈顶元素结果存储在m[nums2[i]]中，并在最后将nums2[i]加入到栈中

  2. 遍历nums1，每次遍历时将其在m中对应结果加入到res中（即res.push_back(m[nums1[i]])）;

    △这种思路同样能引用于在vector中寻找第一个满足于某个条件的元素，只需要通过单调栈+反向遍历的方式即可，在遍历时循环判断若当前栈顶元素满足时遍历元素是否一定满足，若是则弹出栈顶元素即可。最后再将遍历元素加入到栈顶元素中。

    以下为C++代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
            //考虑使用单调栈+哈希表的方式
            stack<int> s;
            map<int,int> m;
            vector<int> res;
            //构建nums2的单调栈和结果哈希表
            int len2=nums2.size();
            int len1=nums1.size();
            for(int i=len2-1;i>=0;--i){
                while(!s.empty()&&nums2[i]>=s.top()){
                    s.pop();
                }
                m[nums2[i]]=s.empty()?-1:s.top();
                s.push(nums2[i]);
            }

            //nums1根据nums2的结果哈希表获取最终结果加入res
            for(int i=0;i<len1;++i){
                res.push_back(m[nums1[i]]);
            }

            return res;
        }
    };