Day62 单调栈part01

时间:2024-07-10 07:05:57

LC739每日温度(未掌握)

  1. 暴力解法:两层for循环,时间复杂度O(n^2),会超时
  2. 未掌握原因分析:只想到了从栈顶到栈底是递减的情况,忽略了从栈顶到栈底是递增的情况
  • 因为需要找到一个元素右边第一个更大元素,只有递增的时候,栈里要加入一个元素i的时候,才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i
  • 下标i和栈顶元素下标是我们已知的信息,我们需要的也是下标,只有充分利用我们已知的信息才能减轻负担
  1. 代码
    在这里插入图片描述

LC496下一个更大元素I(未掌握)

  1. 本质是跟LC739一样的,但是因为涉及两个数组,所以更绕了一点,需要想到使用map来映射找到右边第一个比它大的元素下标,并判断是否在nums1中存在
  2. 代码
  • 如果nums2某个元素找到了右边第一个比它大的元素
  • 且nums1中包含这个元素
  • 那么result中这个下标存储的元素就是nums2中找到的那个元素
    在这里插入图片描述

LC503下一个更大元素II

  1. 不扩充nums,而是在遍历中模拟走了两边nums
  2. 代码
    在这里插入图片描述