代码随想录算法训练营第五十七天|LeetCode739.每日温度 、LeetCode496.下一个更大元素I

LeetCode 739 每日温度

题目链接:739. 每日温度 - 力扣（LeetCode）

【解题思路】

• 用一个单调栈记录遍历过元素的下标

• 当前元素下标的值比栈顶元素下标的值大

  • 1.将栈顶元素弹出

  • 2.将当前元素入栈

  • 3.result数组记录当前元素的下标

• 当前元素下标的值等于栈顶元素下标的值

  • 直接将当前元素加入单调栈

• 当前元素下标的值比栈顶元素下标的值小

  • 直接将当前元素加入单调栈

【解题步骤】

• 1.定义一个栈st

• 2.定义一个result数组（结果集），大小为T数组的大小，初始化为0

• 3.放入下标0的元素到st栈里

• 4.循环遍历T数组，从下标1开始（0已经放入栈里）

  • 当前遍历元素小于栈顶元素

    • 直接将当前遍历元素下标加入栈里

  • 当前遍历元素等于栈顶元素

    • 直接将当前遍历元素下标加入栈里

  • 当前遍历元素大于栈顶元素

    • 一直将栈顶元素弹出，直到栈顶元素大于当前遍历元素

      • result[st.top()] = i-st.top()

• 5.return result

【代码部分】

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
		int[] result = new int [temperatures.length];
		Deque<Integer> stack = new LinkedList<>();
		stack.push(0);
		for (int i = 1; i < temperatures.length; i++) {
			if(temperatures[i] <= temperatures[stack.peek()]){
				stack.push(i);
			}else{
				while (!stack.isEmpty()&&temperatures[i] > temperatures[stack.peek()]){
					result[stack.peek()] = i-stack.peek();
					stack.pop();
				}
				stack.push(i);
			}
		}
		return result;
    }
}

LeetCode 496 下一个更大元素I

题目链接:496. 下一个更大元素 I - 力扣（LeetCode）

【解题思路】

• 在遍历nums2的过程中，需要判断nums2[i]是否在nums1中出现过

• 可以用map做银蛇，根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过

• 情况1：当前遍历的元素小于栈顶元素

  • 直接入栈

• 情况2：当前遍历的元素等于栈顶元素

  • 直接入栈

• 情况3：当前遍历的元素大于栈顶元素

  • 判断栈顶元素是否在nums1中出现过，如果出现过，记录结果

【解题步骤】

• 【解题步骤】

  • 1.定义一个栈st

  • 2.定义一个result数组（结果集），大小为nums1的大小，初始化为0

  • 3.将result数组内所有元素初始化为-1

  • 4.创建一个HashMap，用来匹配元素

  • 5.遍历nums1，将nums1的元素和下标记录到HashMap中

  • 6.将st的第一个元素初始化为0（将0放入st中）

  • 7.遍历nums2

    • 如果nums2[i]小于等于nums2[st.peek()]

      • 直接将当前元素下标入栈

    • 如果nums2[i]大于nums2[st.peek()]

      • 如果nums2[st.peek()]在哈希表中能找到

        • Integer index = hashMap.get(nums2[temp.peek()]);

        • result[index] = nums2[i];

      • 一直弹出栈顶元素，直到当前元素小于栈顶元素

    • 将当前下标添加进st中

  • 8.return result

【代码部分】

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
		Stack<Integer>st = new Stack<>();
		int[]result = new int[nums1.length];
		Arrays.fill(result,-1);
		HashMap<Integer,Integer>hashMap = new HashMap<>();
		for (int i = 0; i < nums1.length; i++) {
			hashMap.put(nums1[i],i);
		}
		st.add(0);
		for (int i = 1; i < nums2.length; i++) {
			if(nums2[i] <= nums2[st.peek()]){
				st.add(i);
			}else {
				while (!st.isEmpty()&&nums2[i] > nums2[st.peek()]){
					if(hashMap.containsKey(nums2[st.peek()])){
						Integer index = hashMap.get(nums2[st.peek()]);
						result[index] = nums2[i];
					}
					st.pop();
				}

			}
			st.add(i);
		}
		return result;
    }
}