2022/05/30 Mon 21:10    2022/11/27 Sun 22:05

单调递减栈：从栈底到栈顶是单调递减的
每次我们移动到数组中一个新的位置 iii，就将当前单调栈中所有小于 nums2[i] 的元素弹出单调栈，
对于单调队列解决问题的模板：for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。while 循环是把两个“高个”元素之间的元素排除，因为他们的存在没有意义，前面挡着个“更高”的元素，所以他们不可能被作为后续进来的元素的 Next Great Number 了。
这个算法的时间复杂度不是那么直观，如果你看到 for 循环嵌套 while 循环，可能认为这个算法的复杂度也是 O(n^2)，但是实际上这个算法的复杂度只有 O(n)。
分析它的时间复杂度，要从整体来看：总共有 n 个元素，每个元素都被 push 入栈了一次，而最多会被 pop 一次，没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的，也就是 O(n) 的复杂度。

leetcoad496-下一个更大的元素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]
解释：（这里的解释算是比较的清楚的表述的）
对于num1中的数字4，在num2中不存在下一个更大元素，所以答案是 -1 。
对于num1中的数字1，在num2中存在下一个更大元素是 3 。
对于num1中的数字2，在num2中不存在下一个更大元素，所以答案是 -1 。

示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
对于num1中的数字2，在num2中存在下一个更大元素是 3 。
对于num1中的数字4，在num2中不存在下一个更大元素，所以答案是 -1 。

直接暴力解法：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 采用暴力的解法来解题
        # 定义一个结果数组，用来存放最后的值
        n=len(nums1)
        res=[-1]*n
        # 在nums1中进行遍历
        for i in range(n):
            # 在nums2中遍历,找到与nums1[i]相同的值nums2[j]
            for j in range(len(nums2)):
                if nums2[j]==nums1[i]:
                    # 然后在nums2[j]右侧继续找，找到一个比他大的数出来
                    for k in range(j+1,len(nums2)):
                        if nums2[k]>=nums2[j]:
                            res[i]=nums2[k]
                            break
        return res

思路分析：（借助栈来遍历分析）

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 若数组为空，直接返回空
        if not nums1:
            return []
        n=len(nums1)
        ans=[-1]*n
        # 倒着往栈里面放元素
        for i in range(n-1,-1,-1):
            # nums2.index(nums1[i]) 表示当遍历的元素是nums1[i]的时候，此时的这个元素在nums2中的下标是多少,
            # 用temp_index存储，表示临时下标的意思
            # 由于我们需要寻找nums2中对应位置的右侧，也就需要在nums2的[temp_index:]这个区间里面去找是否有比nums1[i]大的数
            temp_index=nums2.index(nums1[i])
            s=nums2[temp_index:][::-1]
            # 栈不为空，并且栈顶元素不超过当前遍历的元素
            while s and nums1[i]>=s[-1]:
                # 把当前的栈顶元素弹开
                s.pop()
            # while循环结束
            # 如果当前栈有值，直接将栈顶值赋给ans[i],表示存在
            ans[i]=s[-1] if s else -1
        return ans

看到官方的题解尽然可以优化：单调栈+哈希表

from typing import List
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        hashmap = {}
        stack = []
        # 对反转之后的nums2进行遍历
        for num in reversed(nums2):
            # 当栈顶元素不为空，并且栈顶元素小于当前遍历的元素的时候
            # 将栈顶的元素进行弹出
            while stack and num >= stack[-1]:
                stack.pop()
            # 内循环结束之后，如果如果栈不为空，那么哈希表中遍历的值为栈顶的元素，如果栈为空，说明此时=右侧没有比他更大的数，直接返回-1
            hashmap[num] = stack[-1] if stack else -1
            # 将当前的num值加入栈中
            stack.append(num)
        # 返回的值需要注意，遍历nums1,用相应的num值哈希表hashmap中去寻找
        ans=[hashmap[num] for num in nums1]
        # 上面的是用的表达式求值，写起来要相对简洁一点；如果实际做题的时候不够熟练，可以用常规的方式来解题
        # ans=[]
        # for num in nums1:
        #     temp=hashmap.get(num)
        #     ans.append(temp)
        return ans

if __name__=='__main__':
    nums1=[4,1,2]
    nums2=[1,3,4,2]
    res=Solution().nextGreaterElement(nums1,nums2)
    print(res)

leetcoad503-下一个更大的元素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]

思路分析：因为用到了最小栈与最小队列的思想

ToTOP
2018 bear