LeetCodeCampsDay48单调栈part01

初识单调栈

单调栈

什么时候用单调栈呢？

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

如果暴力求解，比如两层for循环，时间复杂度是O(n^2)

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

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

更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。

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

单调栈里存放的元素是什么？

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

单调栈里元素是递增呢？还是递减呢？

注意以下讲解中，顺序的描述为从栈头到栈底的顺序，因为单纯的说从左到右或者从前到后，不说栈头朝哪个方向的话，大家一定比较懵。

使用单调栈主要有三个判断条件。

当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

把这三种情况分析清楚了，也就理解透彻了。

接下来我们用temperatures = [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析，输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

首先先将第一个遍历元素加入单调栈

739.每日温度1

加入T[1] = 74，因为T[1] > T[0]（当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况）。

我们要保持一个递增单调栈（从栈头到栈底），所以将T[0]弹出，T[1]加入，此时result数组可以记录了，result[0] = 1，即T[0]右面第一个比T[0]大的元素是T[1]。

739.每日温度2

加入T[2]，同理，T[1]弹出

739.每日温度3

加入T[3]，T[3] < T[2] （当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况），加T[3]加入单调栈。

739.每日温度4

加入T[4]，T[4] == T[3] （当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况），此时依然要加入栈，不用计算距离，因为我们要求的是右面第一个大于本元素的位置，而不是大于等于！

739.每日温度5

加入T[5]，T[5] > T[4] （当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况），将T[4]弹出，同时计算距离，更新result

739.每日温度6

T[4]弹出之后， T[5] > T[3] （当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况），将T[3]继续弹出，同时计算距离，更新result

739.每日温度7

直到发现T[5]小于T[st.top()]，终止弹出，将T[5]加入单调栈

739.每日温度8

加入T[6]，同理，需要将栈里的T[5]，T[2]弹出

739.每日温度9

同理，继续弹出

739.每日温度10

此时栈里只剩下了T[6]

739.每日温度11

加入T[7]， T[7] < T[6] 直接入栈，这就是最后的情况，result数组也更新完了。

739.每日温度12

此时有同学可能就疑惑了，那result[6] , result[7]怎么没更新啊，元素也一直在栈里。

其实定义result数组的时候，就应该直接初始化为0，如果result没有更新，说明这个元素右面没有更大的了，也就是为0。

以上在图解的时候，已经把，这三种情况都做了详细的分析。

情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

通过以上过程，大家可以自己再模拟一遍，就会发现：只有单调栈递增（从栈口到栈底顺序），就是求右边第一个比自己大的，单调栈递减的话，就是求右边第一个比自己小的。

739. 每日温度

https://leetcode.cn/problems/daily-temperatures/

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

示例 1:

1 2	输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

示例 2:

1 2	输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]

示例 3:

1 2	输入: temperatures = [30,60,90] 输出: [1,1,0]

提示：

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

单调栈思路

使用单调栈，栈底元素是最大的

先将第一个元素入栈，栈内记录这个元素的下标

从第二个元素开始遍历，如果num[i]小于栈Top元素则直接入栈

如果num[i]大于栈Top元素则将栈Top弹出，并且res[j]=i-j（假设j为栈Top元素的值)，表示第j天右边第一个更大的元素是（i-j)天后

单调栈代码

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]: 
        stack = list()
        stack.append(0)

        L = len(temperatures)
        res = [0] * L
        for i in range(1, L):
            # 如果temper[i]更小，直接添加进入
            if temperatures[i] <= temperatures[stack[-1]]:
                stack.append(i)
            else:
                # 如果temper[i]更大，先将栈中小于temper[i]的都弹出来
                while stack and temperatures[i] > temperatures[stack[-1]]:
                    j = stack.pop()
                    res[j] = i - j
                stack.append(i)

        return res

496. 下一个更大元素 I

https://leetcode.cn/problems/next-greater-element-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] 是如上所述的 下一个更大元素 。

示例 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) 的解决方案吗？

单调栈思路

线索1、nums2里所有数字不同

线索2、nums1是nums2子集

问题可以变成：先求nums2里的每个元素的下一更大元素（使用单调栈）

再想办法把nums1和nums2映射，可以考虑桶排序（因为本题目的数字范围不大），如果数字范围大，则需要使用map进行映射

单调栈代码（普通）

时间复杂度O(N * M)
空间复杂度O(M)

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = list()
        stack.append(0)

        L2 = len(nums2)
        biggerNums2 = [-1] * 10000
        for i in range(1, L2):

            if nums2[i] <= nums2[stack[-1]]:
                stack.append(i)
            else:
                while stack and nums2[stack[-1]] < nums2[i]:
                    j = stack.pop()
                    biggerNums2[nums2[j]] = nums2[i]
                stack.append(i)


        res = []
        for i in nums1:
            res.append(biggerNums2[i])
        
        return res

或者使用python自带的index函数，直接调用nums1.index(nums2[stack[-1]])

单调栈代码（优化）

时间复杂度O(N * M)
空间复杂度O(M)

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = list()
        stack.append(0)

        L2 = len(nums2)
        # 默认值都为-1
        res = [-1] * len(nums1)
        for i in range(1, L2):
            # 如果新数字小于栈顶值，就无脑添加进来
            if nums2[i] <= nums2[stack[-1]]:
                stack.append(i)
            else:
                while stack and nums2[stack[-1]] < nums2[i]:
                    if nums2[stack[-1]] in nums1:
                        # 找到nums2[i]在nums1对应下标
                        index = nums1.index(nums2[stack[-1]])
                        # 添加到答案组里
                        res[index] = nums2[i]
                    # 注意这个pop操作，不论nums2[stack[-1]]是否在nums1都要执行
                    stack.pop()
                stack.append(i)
        return res

503. 下一个更大元素 II

https://leetcode.cn/problems/next-greater-element-ii/

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

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

示例 1:

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

1 2	输入: nums = [1,2,3,4,3] 输出: [2,3,4,-1,4]

提示:

1 <= nums.length <= 104
-109 <= nums[i] <= 109

单调栈思路

找下一个更大的元素，可以使用单调栈

单调递减栈，栈底是整个栈最大值

stack初始化添加下标0

从下标1开始遍历（进行循环遍历一次，从1到(1+len(nums))），若nums[i]大于stack[-1]（指栈顶值）则将栈顶值弹出，并且res[j] = nums[i]（j表示栈顶值元素在nums里的下标值）

如果nums[i]小于stack[-1]，则直接将nums[i]添加进去

单调栈代码

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        stack = list()
        stack.append(0)

        L = len(nums)
        res = [-1] * L
        for i in range(2 * L):
            if nums[i % L] <= nums[stack[-1]]:
                stack.append(i % L)
            else:
                while stack and nums[i % L] > nums[stack[-1]]:
                    j = stack.pop()
                    res[j] = nums[i % L]
                stack.append(i % L)

        return res