Day 58
739. 每日温度
- 情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
- 情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
- 情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:result = [0] * len(temperatures)stack = [0]for i in range(1, len(temperatures)):if temperatures[i] <= temperatures[stack[-1]]:stack.append(i)else:while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:result[stack[-1]] = i - stack[-1]stack.pop()stack.append(i)return result
class Solution {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;}
}
496.下一个更大元素 I
- 情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
此时满足递增栈（栈头到栈底的顺序），所以直接入栈。
- 情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！
- 情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。
判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果。
记录结果这块逻辑有一点小绕，要清楚，此时栈顶元素在nums2数组中右面第一个大的元素是nums2[i]（即当前遍历元素）。
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:result = [-1] * len(nums1)stack = [0]for i in range(1, len(nums2)):if nums2[i] <= nums2[stack[-1]]:stack.append(i)else:while len(stack) != 0 and nums2[i] > nums2[stack[-1]]:if nums2[stack[-1]] in nums1:index = nums1.index(nums2[stack[-1]])result[index] = nums2[i]stack.pop()stack.append(i)return result
