代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
1. LeetCode 739. 每日温度
1.1 思路
- 本题按照正常的暴力解法大概率过不了，是一个 n^2 的时间复杂度，本题用到一个单调栈的解法。
- 单调栈适用场景：求当前元素左边或者右边第一个比当前元素大或者小的元素。而本题求的就是当前位置右边第一个比其大的元素，两个位置下标一相减就是了
- 什么是单调栈：就是一个栈，但栈里的元素要保证是递增或者递减的。一般编程语言没有实现这种栈的，只能自己模拟实现。本题中我们放入栈的不应该是元素本身，因为本题元素有重复，无法锁定唯一下标，而且我们要找的是下标相减的值，因此我们应该直接存下标，我们知道下标了直接用数组映射就是对应的元素的大小。
- 从栈顶到栈底的顺序：递增还是递减？如果是递增，求的就是左边或者右边第一个比当前位置大的元素，如果加入的元素大于栈顶的元素，才找到栈顶的元素在这个数组里所对应的右边第一个元素的位置；如果是递减，求的就是左边或者右边第一个比当前位置小的元素。注意这里的递增递减是从栈顶到栈底的方向
- 单调栈的作用：存放遍历过的元素。时间复杂度是 O(n)的，用一个 for 循环遍历的，我们是不知道当前元素和之前遍历过的元素之间是大是小，因此用一个数据结构记录遍历过的元素，这个单调栈就是记录遍历过的元素，然后和当前元素比较。那如何存放呢？因为当前遍历的元素就是和栈顶的元素作比较，要么大，要么等于，要么小于，然后做对应的操作。当前元素是 T[i]，栈顶元素是 T[st.peek()]，因为单调栈存的是下标
- 过程：定义个 result 数组存结果。先存第一个元素的下标，如果这个下标对应的数值比当前遍历的元素大，就下标之差，然后存入 result 中，含义就是第一个比 0 下标大的位置。然后如果栈里元素是计算过的就弹出，然后接着把 1 下标的元素加入栈中。后续如果出现当前遍历的元素小于等于栈顶元素的话就把这元素入栈，并且结果先不用记录，一直这样，这个栈从栈顶到栈底就是一个递增的关系。直到出现当前遍历的元素比栈顶大了，才作差然后存入 result 中，注意，这里比较完栈顶出栈，但是当前遍历的元素要接着和栈顶比较，然后作差存入 result 中，直到当前遍历的元素小于等于栈顶了，然后才把当前遍历元素存入栈顶。一直这样进行下去到最后可能会有元素在栈里没出来，说明右边没有比它大的元素了，那就默认为 0 即可
- 代码实现：Stack stack；int[] result=new int[T.length]；stack.push(0)第一个元素存的是下标 0；for（int i=1；i<T.length；i++）从 1 开始是因为 0 下标已经存入栈了。如果当前元素小于等于栈顶元素就直接入栈，记住存的是下标。如果大于，while（!stack.empty()&&T[i]>T[stack.peek()]）栈不能为空，用 while 是因为当前元素一直比栈顶大就要一直比较下去，result[stack.peek()]=i-stack.peek()，然后出栈 stack.pop()。最终 return result 即可。
1.2 代码
class Solution { // 版本 1 public int[] dailyTemperatures(int[] temperatures) { int lens=temperatures.length; int []res=new int[lens]; /** 如果当前遍历的元素 大于栈顶元素，表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素， 所以弹出 栈顶元素，并记录 如果栈不空的话，还要考虑新的栈顶与当前元素的大小关系 否则的话，可以直接入栈。 注意，单调栈里 加入的元素是 下标。 */ Deque<Integer> stack=new LinkedList<>(); stack.push(0); for(int i=1;i<lens;i++){ if(temperatures[i]<=temperatures[stack.peek()]){ stack.push(i); }else{ while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){ res[stack.peek()]=i-stack.peek(); stack.pop(); } stack.push(i); } } return res; } }
2. LeetCode 496. 下一个更大元素 I
2.1 思路
- 本题给了两个数组，nums1 是 nums2 的子集，各自没有重复的元素。在 nums2 中找出 nums1 中元素 x 第一个比其大的元素，存入新数组中，如果没有就是存入-1，这个新数组的大小和 nums1 一样。本质就是求在 nums2 中比当前元素 x 的右边第一个比其大的数，注意是从同一个元素的右边出发，而不是从下标 0 出发。在739. 每日温度就是一道直接的单调栈的题目，本题绕了一下。
- 首先定义个 result 数组，大小和 nums1 是一样的。在739. 每日温度中默认值都是 0，但在本题中找不到右边第一个比 x 大元素的话应该存的是-1。
- 单调栈应该遍历哪个数组呢？因为要求的是 nums2 里某个元素右边第一个比其大的元素是多少，因此遍历的是 nums2。单调栈里存入的是遍历过的元素
- 两个数组的联系是什么？比如在 nums2 中找到了元素 2 右边第一个比 2 大的元素是 3，那么就根据 2 找到 nums1 中有没有 2，如果有要找到 2 的下标，然后在 2 的下标的位置存入 3，因此要建立一个哈希映射。需要在 nums2 中的元素找到在 nums1 中是否出现过，如果出现过就找到这个元素的下标，因此用一个 map<k，v>。
- 单调栈顶到栈底的顺序是递增还是递减？因为求的是右边第一个比当前元素大的，因此用递增，并且存的是下标。然后还是当前元素和栈顶元素的比较，大于等于小于，栈顶元素是 nums2[stack.top()]，当前元素是 nums2[i]。
- 代码实现：定义个栈、数组，数组和 nums1 大小一样，并且默认值为-1。如果 nums1 为 null 就直接 return null。要做一个映射的逻辑，要先把 nums1 元素映射到 nums2 的下标，因为遍历 nums2 的时候要找到对应 nums1 的下标。HashMap<Interger，Integer>，遍历 nums1，正常的 for 循环，map[nums[i]]=i，k 是值，v 是下标。然后 stack.push(0)，先放入下标 0。然后是 for（int i=1；i<nums2.length；i++）从 1 开始是因为 0 下标已经存入栈了，然后就是单调栈的过程，如果当前元素如果小于等于栈顶元素，那就加入栈，如果大于，while（!stack.empty()&&nums2[i]>nums2[stack.peek()]）用 while 是因为如果一直大于栈顶就要一直比较下去，然后 if（map.containsKey(nums2[stack.peek())）用哈希表看一下栈顶元素是否在 nums1 存在，int index=map.get（nums2[stack.peek()]）找到对应元素在 nums1 的下标，然后 result[index]=nums2[i]，这里不管哈希表是否存在，最后栈顶都要出栈。while 循环结束后把比较的元素放入栈中。最后 return result
2.2 代码
class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { Stack<Integer> temp = new Stack<>(); int[] res = new int[nums1.length]; Arrays.fill(res,-1); HashMap<Integer, Integer> hashMap = new HashMap<>(); for (int i = 0 ; i< nums1.length ; i++){ hashMap.put(nums1[i],i); } temp.add(0); for (int i = 1; i < nums2.length; i++) { if (nums2[i] <= nums2[temp.peek()]) { temp.add(i); } else { while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) { if (hashMap.containsKey(nums2[temp.peek()])){ Integer index = hashMap.get(nums2[temp.peek()]); res[index] = nums2[i]; } temp.pop(); } temp.add(i); } } return res; } }
