这是基于代码随想录的每日打卡
739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
单调栈
寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
就是用一个栈来记录我们遍历过的元素，单调栈里只需要存放遍历过的下标就可以了。
先将第一个元素放进栈中，然后遍历后面的元素，如果遍历到的当前元素比栈口元素小，则继续放入栈中；
如果比栈口元素大，则说明栈口元素找到了第一个比它的值大的元素，符合题意，则弹出栈口元素，同时将两个元素下标对应相减，就是栈口元素的结果值。
还没完，如果栈口元素弹出后，下一个栈口元素还比当前元素小，则继续弹出操作且下标相减存入结果。
这样就保证单调栈里面的值是单调递减，且可以确定栈口是朝右，这样比较容易想象。
栈里保存的是我们的下标值
代码
class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:# 单调栈stack=[0]# 存放结果res=[0]*len(temperatures)# 遍历温度for i in range(1,len(temperatures)):# 当前元素比栈口元素小，则存入if temperatures[i]<=temperatures[stack[-1]]:stack.append(i)# 当前元素比栈口元素大，则一直弹栈直到不符合条件else:while stack and temperatures[i]>temperatures[stack[-1]]:index=stack.pop()res[index]=i-indexstack.append(i)return res
运行结果
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] 是如上所述的 下一个更大元素 。
示例 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 。
单调栈
跟上题一样，构造一个单调栈，栈口朝右，且保证栈内元素单调递减
先将nums2的第一个元素存入栈中，随后遍历nums2的后续元素
遍历过程发现比栈口元素小，则加进栈。
遍历过程发现有比栈口元素大的元素，则将栈口元素弹出，且检查栈口元素有没有在nums1出现过，若有则将res数组对应下标的值修改为当前遍历到的元素，且持续检查栈口元素与当前元素的大小。
代码
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:# 存放结果res=[-1]*len(nums1)# nums2的单调栈，存放的是nums2元素的下标stack=[0]for i in range(1,len(nums2)):# 若当前元素比栈口元素小则进栈，保证单调递减if nums2[i]<=nums2[stack[-1]]:stack.append(i)else:# 若当前元素比栈口元素大则弹出栈口元素while stack and nums2[i]>nums2[stack[-1]]:# 栈口元素的下标index=stack.pop()# 如果栈口元素在nums2出现过if nums2[index] in nums1:# nums2[index]是栈口元素# nums1.index[nums2(index)]是栈口元素在nums1出现的位置res[nums1.index(nums2[index])]=nums2[i]stack.append(i)return res
运行结果
503. 下一个更大元素 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:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
单调栈
只需要把两个nums拼接，再按单调栈的规矩遍历两个nums
不过不用开辟一个二倍长度的数组，只需要对下标取模
注意栈口元素和取结果数组下标时都要取模
代码
class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:# 单调栈(栈口朝右，单调递减),存储的依旧是下标stack=[0]# 数组长度lens=len(nums)# 存放结果res=[-1]*lensfor i in range(1,lens*2):# 遍历到的当前元素小于栈口元素if nums[i%lens]<=nums[stack[-1]%lens]:stack.append(i)# 遍历到的元素大于栈口元素，则一直弹栈，直到栈口元素小于当前元素else:while stack and nums[stack[-1]%lens]<nums[i%lens]:index=stack.pop()res[index%lens]=nums[i%lens]stack.append(i%lens)return res
运行结果
