739 每日温度
题目：
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]
提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
思路
本题其实可以使用暴力解法实现的， 但是力扣的时间复杂度分析的有问题， O(n2)的时间复杂度尽然过不了。
所以只能寻求更简洁的方法， 那就是通过空间换取时间(单调栈思路)
使用单调栈， 如果出现单调递减的情况， 那么就直接入栈， 如果是递增的 ，那么就符合要求。 因为我们栈内存储的是元素的索引。 所以按照题目要求， 可以将分为2种情况讨论
当前元素 > 栈顶元素
当前元素 <= 栈顶元素
因为栈内存储的是数组元素的下标索引。所以这里只需要一次for循环就可以实现，然后找出栈顶元素对应的满足要求的索引， 索引相减 即可得到我们需要的位次。
情况一：当前元素 <= 栈顶元素
如果当前元素 小于等于栈顶元素， 那么就直接将当前元素的索引入栈， 继续往后找 ， 找到满足条件的。
情况二：当前元素 > 栈顶元素
如果比较得到 当前元素大于栈顶元素 ，那么这个元素就是第一个大于栈顶元素的索引， 所以直接索引相减即可得到大于栈顶元素的位次。同时将栈顶元素出栈， 栈顶出栈之后还需要对当前栈顶的元素再做判断， 万一当前栈顶的元素也满足条件呢？ 所以这里就需要使用循环来进行判断。 同时最后还需要将当前元素的索引入栈。
至于更细节的图解分析。 可以看卡哥的代码随想录学习(地址 : 代码随想录 (programmercarl.com))
实现
class Solution { public int[] dailyTemperatures(int[] temperatures) { int []res = new int[temperatures.length]; Stack<Integer> st = new Stack<>(); st.push(0); //先添加进入第一个元素的索引 for(int i =1 ; i < temperatures.length; i++){ //将当前元素的索引加入占 。然后再将比较与栈顶索引代表的元素的大小 if(temperatures[i] > temperatures[st.peek()]){ //需要考虑站内有多个元素的情况 while(!st.isEmpty() && temperatures[i] > temperatures[st.peek()]){ res[st.peek()] = i - st.pop(); //当前元素出栈 } st.push(i); }else { // temperatures[i] <= temperatures[st.peek()] st.push(i); } } return res; } /* 暴力解法 ，超出时间限制 public int[] dailyTemperatures(int[] temperatures) { int [] arr= new int[temperatures.length]; for(int i =0; i < temperatures.length;i++){ for(int j = i; j < temperatures.length ;j++){ if(temperatures[j] > temperatures[i]){ arr[i] = j - i; break; } } } return arr; } */ }
496 下一个更大元素
题目：
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] 解释：nums1 中每个值的下一个更大元素如下所述： - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。 - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
思路
顺着题目要求写即可， 不用使用单调栈的方式， 因为使用暴力的方法时间复杂度可能更低
实现
暴力；
class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int []res = new int[nums1.length]; for(int i =0 ;i < nums1.length; i++){ int j = 0; //首先 先找到nums1[i] == nums2[j] 的j的下标。 然后本层索引才能从j开始 for(; j < nums2.length; j++){ if(nums1[i] == nums2[j]){ break; } } for(; j< nums2.length; j++){ if(nums2[j] > nums1[i] ){ res[i] = nums2[j]; break; } } if(j == nums2.length && res[i] == 0){ res[i] = -1; } } return res; } }
503 下一个更大的元素
题目:
给定一个循环数组 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]
提示:
1 <= nums.length <= 104
-109 <= nums[i] <= 109
思路
就是将nums再赋值一遍， 然后找是否有大于 当前栈顶元素的元素。如果有就添加到res数组中去。但是本题我们实现的时候是通过取余的方式， 这样可以减少遍历的次数。
其实没啥差别：
实现
class Solution { public int[] nextGreaterElements(int[] nums) { //边界判断 if(nums == null || nums.length <= 1) { return new int[]{-1}; } int size = nums.length; int []nums1 = new int[2*size]; for(int i= 0 ;i < 2*size; i++){ if(i >= size){ nums1[i] = nums[i-size]; }else{ nums1[i] = nums[i]; } } int[] result = new int[2*size];//存放结果 Arrays.fill(result,-1);//默认全部初始化为-1 Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标 for(int i = 0; i < 2*size; i++) { while(!st.empty() && nums1[i] > nums1[st.peek()]) { result[st.peek()] = nums1[i];//更新result st.pop();//弹出栈顶 } st.push(i); } int []temp = new int[size]; for(int i=0 ; i< temp.length; i++){ temp[i] =result[i]; } return temp; } }
优化之后的：
class Solution { public int[] nextGreaterElements(int[] nums) { //边界判断 if(nums == null || nums.length <= 1) { return new int[]{-1}; } int size = nums.length; int[] result = new int[size];//存放结果 Arrays.fill(result,-1);//默认全部初始化为-1 Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标 for(int i = 0; i < 2*size; i++) { while(!st.empty() && nums[i % size] > nums[st.peek()]) { result[st.peek()] = nums[i % size];//更新result st.pop();//弹出栈顶 } st.push(i % size); } return result; } }
42 接雨水
题目：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
