【C++编程能力提升】

一、739 每日温度

题目链接：739 每日温度

核心：对于一维数组，当寻找某个元素的右边或左边第一个比自己大或小的元素的位置，此时需要使用单调栈。对于本题，需要求解某个元素的右边第一个比自己大的元素的位置，就需要使用递增栈（从栈顶到栈底递增）。
遍历数组元素时与栈顶元素比较存在3种情况：其一是当前遍历元素小于栈顶元素，此时符合递增栈，直接入栈；其二是当前遍历元素等于栈顶元素，此时也符合“递增栈”，直接入栈；其三是当前遍历元素大于栈顶元素，此时不符合递增栈，因此需要先将栈中元素弹出，直至push当前元素后仍然符合递增栈。在弹出栈顶元素时，也就是找到了栈顶元素右边第一个比自己大的元素（当前遍历元素）。
求解位置（距离）说明入栈时仅使用下标即可，无需使用元素值。

    vector<int> dailyTemperatures(vector<int>& temperatures) {
//转换为求解一个元素右边第一个大于自己的元素，使用递增栈
//递增栈：从栈顶到栈底递增，每push一个元素都得与栈中元素比较，大于栈中元素说明要先弹出栈中元素，再入栈，保证递增顺序，弹出栈中元素时也就是找到了该弹出元素右边的第一个较大值就是待入栈的元素
    stack<int> stk;  //递增栈
    vector<int> res(temperatures.size(),0);  //记录下标之差，即当前元素与右边第一个大于自己元素的距离
    stk.push(0); //栈中存放的是下标，无需存放数值，因为下标之差即距离
    for(int i=1;i<temperatures.size();++i)
    {//已经把第一个元素push到栈，故从第二个元素开始遍历
        if(temperatures[i]<temperatures[stk.top()])
            stk.push(i); //小于栈顶元素则入栈，说明该元素不是大于栈中元素
        else if(temperatures[i]==temperatures[stk.top()])
            stk.push(i); //与栈顶元素相等时也直接入栈
        else
        {
            while(!stk.empty() && temperatures[i]>temperatures[stk.top()])
            {
                res[stk.top()]=i-stk.top(); //下标之差即元素之间的距离
                stk.pop(); //弹出
            }    
            stk.push(i); //弹出所有小于待入栈元素的栈中元素时才入栈，保证递增
        }
    }
    return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二、496 下一个更大元素I

题目链接：496 下一个更大元素I

核心：求解某元素右边比自己大的元素值，同样使用递增栈，此时某元素是nums1中的各元素，因此返回的res大小与nums1相同；而寻找的比自己大的元素值是在nums2中的元素，因此遍历的是nums2元素，即入栈的是nums2元素的下标。
由于nums1和nums2各元素都不重复，因此可以使用unordered_map将nums1元素映射到map，key是nums1元素值，value是下标值。
当遍历nums2元素和栈顶元素相比较时，需要确定此栈顶元素是否在nums1中，如果在则需要进一步确定更大元素值，否则跳过。

    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
//记录的返回值res是nums1各元素的下一个更大元素值，而此更大元素值是在nums2中确定的
    stack<int> stk;//递增栈
    vector<int> res(nums1.size(),-1); //初始化为-1，因为未找到符合条件的元素时是-1

    //将nums1数组元素映射到map，key是元素值，value是下标值
    unordered_map<int,int> umap; 
    for(int i=0;i<nums1.size();++i)
        umap[nums1[i]]=i;
    
    stk.push(0); //先push第一个元素
    for(int i=1;i<nums2.size();++i)
    {//遍历的数组是nums2，因为要找到的更大元素值是在nums2中
        if(nums2[i]<nums2[stk.top()])
            stk.push(i); //当前元素小于栈顶元素，符合递增
        else if(nums2[i]==nums2[stk.top()])
            stk.push(i); 
        else
        {//当前元素大于栈顶元素时不是直接弹出栈顶元素，而是先判断是否在nums1
            while(!stk.empty() && nums2[i]>nums2[stk.top()])
            {
                if(umap.count(nums2[stk.top()])>0)
                {
                    int index=umap[nums2[stk.top()]]; //确定栈顶元素在nums1的下标
                    res[index]=nums2[i];  //更大元素值就是当前遍历的元素
                }
                stk.pop(); //弹出
            }
            stk.push(i); //弹出应该弹出的元素后再将当前元素下标入栈
        }
    }
    return res;
    }
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
27
28
29
30
31
32
33