每日一题：单调栈系列
1、题目一：496. 下一个更大元素I
给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
1-1、方法：暴力解法
说明：对nums1中的每个元素进行搜索，然后在nums2中找到对应的元素位置，继续在该位置之后查找是否有比该值更大的值，如果存在就放入结果中，如果不存在，赋值-1。时间复杂度高：
O
(
n
2
)
O(n^2)
O
(
n
2
)
。
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
### 1、暴力解法
result = []
for i in range(len(nums1)):
flag = False
for j in range(len(nums2)):
if nums1[i] == nums2[j]:
flag = True
break
if flag is False or j==len(nums2):
result.append(-1)
else:
flag = False
for k in range(j+1, len(nums2)):
if nums2[k]>nums1[i]:
result.append(nums2[k])
flag = True
break
if flag is False:
result.append(-1)
return result
执行用时：204 ms, 在所有 Python3 提交中击败了10.71%的用户
内存消耗：14.9 MB, 在所有 Python3 提交中击败了69.57%的用户
1-2、单调栈解法
单调栈：从栈顶到栈底元素是有顺序的，相关细节参考网上内容，这里我主要提供思路。
说明：该题目可以先不管nums1，可以考虑对问题进行转换：寻找nums2中每个元素对应下一个更大元素的值，如果不存在就赋值-1，最后放到字典中。
然后再回来nums1，迭代元素，找到字典中的key和value进行赋值即可。
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
# ### 1、暴力解法
# result = []
# for i in range(len(nums1)):
# flag = False
# for j in range(len(nums2)):
# if nums1[i] == nums2[j]:
# flag = True
# break
# if flag is False or j==len(nums2):
# result.append(-1)
# else:
# flag = False
# for k in range(j+1, len(nums2)):
# if nums2[k]>nums1[i]:
# result.append(nums2[k])
# flag = True
# break
# if flag is False:
# result.append(-1)
# return result
### 2、单调栈
hashMap = {}
helpStack = []
for i in range(len(nums2)-1, -1, -1):
value = nums2[i]
while len(helpStack)>0 and helpStack[-1]<=nums2[i]:
helpStack.pop()
hashMap[value] = helpStack[-1] if len(helpStack)>0 else -1
helpStack.append(value)
result = []
for i in range(len(nums1)):
result.append(hashMap[nums1[i]])
return result
执行用时：40 ms, 在所有 Python3 提交中击败了90.63%的用户
内存消耗：15.1 MB, 在所有 Python3 提交中击败了30.48%的用户
时间复杂度：求解hashMap的过程时间复杂度为
O
(
l
e
n
g
t
h
2
)
O(length2)
O
(
l
e
n
g
t
h
2
)
，length2为nums2的元素个数，因为每个元素在单调栈中的操作最多是压入弹出分别一次（ps：别被while循环迷惑）。后面在nums1上的时间复杂度就是
O
(
l
e
n
g
t
h
1
)
O(length1)
O
(
l
e
n
g
t
h
1
)
，由于两个操作是顺序而非并行的，所以最终的时间复杂度是
O
(
l
e
n
g
t
h
1
+
l
e
n
g
t
h
2
)
O(length1+length2)
O
(
l
e
n
g
t
h
1
+
l
e
n
g
t
h
2
)
。空间复杂度是
O
(
l
e
n
g
t
h
2
)
O(length2)
O
(
l
e
n
g
t
h
2
)
。
2、题目2：503. 下一个更大元素II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。
说明：主要是一个循环数组，我们可以直接对数组进行拼接，这样问题就转换成和上面解法相同的了，缺点是需要更改数组，增加了空间复杂度。
2-1、暴力解法：明显时间复杂度高
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
# 1、暴力解法，不推荐
length = len(nums)
if length==0:
return []
result = []
for i in range(length-1):
nums.append(nums[i])
print(nums)
for i in range(length):
flag = False
for j in range(i+1, i+length):
if nums[j] > nums[i]:
flag = True
result.append(nums[j])
break
if flag is False:
result.append(-1)
return result
执行用时：3176 ms, 在所有 Python3 提交中击败了9.01%的用户
内存消耗：16.5 MB, 在所有 Python3 提交中击败了16.25%的用户
2-2、单调栈
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
### 2、单调栈解法
length = len(nums)
if length==0:
return []
for i in range(length-1):
nums.append(nums[i])
result = [-1 for i in range(len(nums))]
helpStack = []
for i in range(len(nums)-1, -1, -1):
value = nums[i]
while len(helpStack)>0 and value>=helpStack[-1]:
helpStack.pop()
if len(helpStack)>0:
result[i] = helpStack[-1]
helpStack.append(value)
return result[:length]
执行用时：256 ms, 在所有 Python3 提交中击败了44.40%的用户
内存消耗：16.5 MB, 在所有 Python3 提交中击败了15.19%的用户
2-3、单调栈（能不能不更改原数组？）
能，使用%取余，这样实际的效果等价于于环形数组了。
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
### 3、单调栈（不更改原数组）
length = len(nums)
if length==0:
return []
result = [0 for i in range(length)]
helpStack = []
for i in range(2*length-1, -1, -1):
j = i % length
value = nums[j]
while len(helpStack)>0 and value>=helpStack[-1]:
helpStack.pop()
result[j] = helpStack[-1] if len(helpStack)>0 else -1
helpStack.append(value)
return result
执行用时：244 ms, 在所有 Python3 提交中击败了56.17%的用户
内存消耗：16.4 MB, 在所有 Python3 提交中击败了25.27%的用户
3、题目3：每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
3-1、方法（单调栈：注意存放的是索引）
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
result = [0 for i in range(len(T))]
helpStack = []
for i in range(len(T)-1, -1, -1):
value = T[i]
while len(helpStack)>0 and value>=T[helpStack[-1]]:
helpStack.pop()
result[i] = helpStack[-1]-i if len(helpStack)>0 else 0
helpStack.append(i)
return result
执行用时：600 ms, 在所有 Python3 提交中击败了22.99%的用户
内存消耗：19.1 MB, 在所有 Python3 提交中击败了42.49%的用户