算法模型总结：单调栈

每日温度

739. 每日温度

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

单调栈主要解决寻找数组中下一个比它大的元素的值或者下标。

单调栈问题的结果数组要先初始化，初始化的值为后面没有找到该元素的时候，该位置的值。遍历数组，每一次判断当前元素与栈顶元素的大小。

如果当前元素比栈顶元素小或者等于栈顶元素，直接进行入栈。

如果当前元素比栈顶元素大，则出栈，并循环比较，直到栈为空或者当前元素比栈顶元素小，然后当前元素入栈。

在栈顶元素出栈的时候，则当前元素就是下一个比它大的元素，并且知道栈顶元素的下标，就可以根据要求来进行求解了。

class Solution {
public:
    vector dailyTemperatures(vector& temperatures) {
        stack Monotone_Stack;
        vector result;
        result.resize(temperatures.size());
        for(int i=0;itemperatures[Monotone_Stack.top()])
                {
                    int temp=Monotone_Stack.top();
                    result[temp]=i-Monotone_Stack.top();
                    Monotone_Stack.pop();
                }
                Monotone_Stack.push(i);
            }
        }
        while(!Monotone_Stack.empty())
        {
            result[Monotone_Stack.top()]=0;
            Monotone_Stack.pop();
        }
        return result;
    }
};
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

下一个更大元素

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] 是如上所述的 下一个更大元素 。

本题也使用单调栈来进行解决，即为nums2数组来建立单调栈。

在为nums2数组建立单调栈之前，使用map结构将nums1数组保存起来，它的first是数据，它的second是下标，下标的作用是找到它在结果数组中的位置。使用map结构的好处是查找起来方便，因为vector没有find函数。

建立单调栈的时候，当发生出栈时，判断栈顶元素是否在map中，如果在则执行对应的操作，如果不在则跳过。

class Solution {
public:
    vector nextGreaterElement(vector& nums1, vector& nums2) {
        map map;
        stack stack;
        vector result;
        result.resize(nums1.size(),-1);
        for(int i=0;inums2[stack.top()])
                {
                    if(map.count(nums2[stack.top()])>0)
                    {
                        result[map[nums2[stack.top()]]]=nums2[i];
                    }
                    stack.pop();
                }
                stack.push(i);
            }
        }
        return result;
    }
};
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
34
35
36
37

下一个最大的元素II

503. 下一个更大元素 II

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

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1

这里相当于首尾相接了，直接在原来数组再接一个相同的数组即可。

class Solution {
public:
    vector nextGreaterElements(vector& nums) {
        stack stack;
        vector result;
        nums.insert(nums.end(),nums.begin(),nums.end());  
        result.resize(nums.size(),-1);
        for(int i=0;i=nums[i])
            {
                stack.push(i);
            }
            else
            {
                while(!stack.empty()&&nums[i]>nums[stack.top()])
                {
                    result[stack.top()]=nums[i];
                    stack.pop();
                }
                stack.push(i);
            }
        }
        result.resize(result.size()/2);
        return result;
    }
};
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