1.题目链接:739. 每日温度
题目描述:
给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。
解法:
①此题求右边第一个比它大的数出现在哪 --- 此类型题:求其右边第一个比它大或者小或者等的值在哪等操作用单调栈来解决。
②我们需要一个栈,栈中存的元素是下标,栈中存的就是我们遍历过的元素。我们还需要一个数组大小为数组的长度用于记录最后的结果。
③遍历数组,当遍历的元素大于栈顶元素对应的值,在栈不为空,且遍历的元素大于栈顶元素对应的值的情况下就要更新数组即reslut[st.pop()] = 当前遍历的元素,弹出栈顶元素。直到循环结束后,说明完成了比较,此时我们要将当前遍历的元素压栈。
④当前遍历元素小于或等于栈顶元素对应的值的时候,直接压栈。
⑤因为本题中如果不会升高用0来表示,所以就不用特意初始化了,因为result数组在创建的时候初始化值就是0.
⑥最后返回result数组。
⑦但是此题有点疑惑的就是如果用栈实现时间复杂度就很高,用队列时间就比较低,不懂。
下面为代码(java):
2.题目链接:496. 下一个更大元素 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] 是如上所述的 下一个更大元素 。
解法:
①此题我们要有个数组长度为num1的长度。
②同样的求右边第一个大的问题,用单调栈问题。
③难点就是涉及到了两个数组,我们肯定是要遍历第二个数组的,因为在第二个数组中找第一个右边大的,但是我们最后的结果是根据第一个数组的下标得出的,所以我们要判断在第二个数组中遍历的元素是否在第一个数组中出现过,如果出现过就取一个数组中的值对应的下标更新result数组,所以我们要对第一个数组的下标和值进行映射,故用了map数据结构。
④在result初始化的时候初始化为-1.
⑤剩下的操作和裸单调栈问题一样。
下面为代码(java):
3.总结:
①遇到求右边第一个大的或者小的元素的位置类似的问题用单调栈。
②遇到多个数组下标和值的关系的时候要想到映射。