代码随想录58——单调栈：739每日温度、 496下一个更大元素I

1.739每日温度

参考：代码随想录，739每日温度；力扣题目链接

1.1.题目

1.2.解答

1.2.1.单调栈使用情况

首先想到的当然是暴力解法，两层for循环，把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)

那么接下来在来看看使用单调栈的解法。

那什么时候用单调栈呢？

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

例如本题其实就是找找到一个元素右边第一个比自己大的元素。此时就应该想到用单调栈了。

1.2.2.本题解答

那么单调栈的原理是什么呢？为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢？

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是只需要遍历一次。

在使用单调栈的时候首先要明确如下几点：

• 单调栈里存放的元素是什么？
  单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。

• 单调栈里元素是递增呢？ 还是递减呢？
  假设栈的开口向右，则单调栈里的元素需要从左向右递减。

后面关于单调栈工作原理的绘图直接去看代码随想录中的图就可以了，因为图比较多，这里就不直接给出了。

注意：这里主要理解一下单调栈的工作原理，实际上和汉诺塔非常相似。

• 所谓单调栈，也就是栈中维护的都是单调的值，从栈底到栈顶要么单调递增， 要么单调递减，这里以本题的单调递减为例；
• 新来了一个数之后，就判断它是否比栈顶的数小（或等），如果满足则可以入栈，这样仍然满足单调递减的栈的要求。如果不满足，则就要出栈，在出栈的过程中，我们就在计算最终的结果。

最后给出代码如下，其实思路很简单，但是也非常巧妙，轻易不容易想到。

vector<int> dailyTemperatures(vector<int> &temperatures)
{
    stack<int> st;       // 定义单调栈，存储每个元素的索引
    vector<int> result(temperatures.size(), 0);  // 存储结果，初始化成0 
    st.push(0);   // 先存入第一个数

    // 遍历所有元素，根据大小判断是否要加入单调栈中
    for(int i = 1; i < temperatures.size(); i++)
    {
        // 1.如果当前元素 < 栈顶元素，则入栈
        if(temperatures[i] < temperatures[st.top()])
            st.push(i);
        // 2.如果当前元素 = 栈顶元素，则入栈
        else if(temperatures[i] == temperatures[st.top()])
            st.push(i);  
        // 3.如果当前元素 > 栈顶元素，开始出栈
        else 
        {
            while(!st.empty() && temperatures[i] > temperatures[st.top()])
            {
                // 计算结果，看右边是第几个数比当前的数大。这里也可以发现为什么单调栈中
                // 存储的是元素的索引，而不是元素的值，因为我们这里就要通过索引来计算有
                // 几个数，如果存储元素值的话虽然可以用于比较大小，但是无法计算有几个数
                result[st.top()] = i - st.top();    
                st.pop();   // 弹出
            }
            // 运行到这里，说明当前元素可以入栈，入栈后仍然是单调栈
            st.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

2. 496下一个更大元素I

参考：代码随想录，496下一个更大元素I；力扣题目链接

2.1.题目

2.2.解答

其实这道题目和上一道题目几乎是一样的。我们把nums2就看成是上一题中给的数组，然后计算nums2中每个元素的右边第一个大于它的数。但是和上一题不同是，这里需要计算的是nums1 中的数值，其实这个时候只需要在num2中的数出栈的时候判断要出栈的数是否在num1中即可，如果在的话就存储结果，如果不在则直接出栈即可，不需要存储结果。

另外一个小的trick是，本题求得是数，而不是索引，所以在栈中直接存数值就可以了。

给出代码如下，其实思路非常简单，和上面的题目几乎一样。

vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
{
	// 1.定义变量
	stack<int> st;   // 单调栈，这里直接存数据就可以了
	vector<int> result(nums1.size(), -1);   // 最终结果，初始化成-1   
	
	// 2.记录nums1的数据和对应的索引，方便后面查找。因为使用单调栈之后给结果
	//   赋值的时候不一定是按照从前向后的顺序赋值的，所以这里要记录元素对应的索引
	unordered_map<int, int> umap;
	for(int i = 0; i < nums1.size(); i++)
	    umap[nums1[i]] = i;
	
	st.push(nums2[0]);   // 先把nums2的第一个数加入
	// 3.遍历nums2，用单调栈求右边第一个大于当前数的数据
	for(int i = 1; i < nums2.size(); i++)
	{
	    // (1)如果满足单调栈的要求，则入栈
	    if(nums2[i] <= st.top())
	        st.push(nums2[i]);
	    // (2)否则不满足要求，则不断出栈，出栈过程中收集结果
	    else 
	    {
	        while(!st.empty() && nums2[i] > st.top())
	        {
	            // 如果栈顶的数是nums1中的数，则可以收集结果
	            if(umap.find(st.top()) != umap.end())
	            {
	                result[umap[st.top()]] = nums2[i];
	            }
	            st.pop();   // 不管是否收集结果，都要出栈
	        }
	        // 运行到这里，则当前数字可以入栈
	        st.push(nums2[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
38
39