496.下一个更大元素I
难度：简单
题目：
给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
提示：
- 1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 104
- nums1和nums2中所有整数 互不相同
- nums1 中的所有整数同样出现在 nums2 中
示例：
示例 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 。
分析
暴力解法
先来说说暴力解法，虽然是暴力，但只是算法层面的，该维护的字典空间还是要维护的。 我们创建一个空字典d，用于将nums2中每个元素对应的第一个比它大的元素进行记录。 将nums2从 index[i]
开始，双层for循环，判断从index[i + 1] 到index[len(nums2) -1]为止， 当遇到有比 index[i] 大的数，终止循环，并将该数加入字典d中。
然后我们开始循环nums1，使用d.get(nums1[index],-1)的方式，可以将没有找到下一个最大值的数直接返回-1。
使用暴力解法，时间复杂度为len(nums2) ** 2,这道题没有超时，只能说侥幸...
单调栈
使用单调栈，可以让我们在len(nums2)的时间复杂度内完成这道题目。 创建字典d，并记录nums2中下一个比当前元素大的数字方式不变。但此时，我们将之前的双层for循环改为单调栈模式。
初始化stack = []
入栈场景：
- 栈为空
- 栈顶元素，比当前元素大
出栈场景：
- 出栈场景为循环判断
- 当前元素 num 比栈顶元素大，则栈顶出栈，并将d[stack[-1]] = num
- 继续执行2操作，直到栈为空、或者栈顶元素大于当前元素时，停止出栈
- 将当前元素入栈
这样的单调栈操作，我们只使用了O(n)的时间复杂度，就完成了所有判断。 最后，循环nums1获取hash表d中对应的值即可。
暴力法解题：
class Solution:
def nextGreaterElement(self, nums1, nums2):
d, ln = {}, len(nums2)
for index, num in enumerate(nums2):
for i in range(index + 1, ln):
if nums2[i] > num:
d[num] = nums2[i]
break
return [d.get(j, -1) for j in nums1]
单调栈解题：
class Solution:
def nextGreaterElement(self, nums1, nums2):
d, stack = {}, []
for num2 in nums2:
while stack and num2 > stack[-1]:
d[stack.pop()] = num2
stack.append(num2)
return [d.get(j, -1) for j in nums1]
503.下一个更大元素II
难度：中等
题目：
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的
下一个更大的数。如果不存在，则输出 -1。
注意: 输入数组的长度不会超过 10000。
示例：
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
分析
暴力法
简单粗暴的方式，当然对于每一个元素，进行最大两倍nums下标长度的循环，如果找到比该元素大的数，记录并终止。
这样的O(n ^ 2)的时间复杂度，面对10 ^ 5长度范围，堪堪能通过，python 4000ms.
暴力法
单调栈
做过这道题的简化版本题目：
就了解应该是使用单调栈的方式进行解题了。
首先我们维护一个ret = [-1] * len(nums)的数组，然后循环两次nums，使用单调栈的方式存储下标。
如果找到比栈顶大的元素，则对栈内存储的下标对应的ret赋值。
单调栈
单调栈优化
上面的单调栈解法，代码会很简洁，但是效率不够完美，因为我们进行了数据的二次进栈，造成了很多不必要的内存和计算开销。
那么，为了优化算法，我们可以牺牲代码的简洁性，分两次循环，在第二次循环时，只判断栈内数据是否可以出栈，而不做重复的
二次进栈操作，这样可以提升效率...
单调栈优化
暴力解题：
class Solution:
def nextGreaterElements(self, nums):
ln = len(nums)
ret = [-1] * ln
point = 0
while point < ln:
for i in range(point + 1, 2 * ln):
if nums[i % ln] > nums[point]:
ret[point] = nums[i % ln]
break
point += 1
return ret
单调栈解题：
class Solution:
def nextGreaterElements(self, nums):
ln = len(nums)
ret = [-1] * ln
stack = []
for i in range(ln * 2 - 1):
while stack and nums[stack[-1]] < nums[i % ln]:
ret[stack.pop()] = nums[i % ln]
stack.append(i % ln)
return ret
单调栈优化解题：
class Solution:
def nextGreaterElements(self, nums):
ln = len(nums)
ret = [-1] * ln
stack = []
for index, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
ret[stack.pop()] = num
stack.append(index)
ind = 0
while stack and ind < ln:
while stack and nums[ind] > nums[stack[-1]]:
ret[stack.pop()] = nums[ind]
ind += 1
return ret
739.每日温度
难度：中等
题目：
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。
如果气温在这之后都不会升高，请在该位置用 0 来代替。
提示：
- 气温列表长度的范围是 [1, 30000]
- 每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
示例：
给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
分析
做过这道题的通类似题目：
就了解应该是使用单调栈的方式进行解题了。大家可以看看我对之前这两道的题解。相信对你理解这道题有所帮助。
具体代码实现思路如下：
- 我们维护一个与temperatures 等长的 ret 全零数组。
- 创建一个stack作为单调栈
- 当栈为空或当前index对应的温度，小于栈顶index对应的温度时，index入栈
- 循环温度当栈不为空且当前温度大于栈顶时，栈顶出栈、记录index差值、并对应ret的index进行赋值，最后入栈index。
解题：
class Solution:
def dailyTemperatures(self, temperatures):
ln = len(temperatures)
ret = [0] * ln
stack = []
for i in range(ln):
while stack and temperatures[i] > temperatures[stack[-1]]:
index = stack.pop()
ret[index] = i - index
stack.append(i)
return ret
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
网友评论