【随想录】Day57—第九章 动态规划part17

本文主要是介绍【随想录】Day57—第九章 动态规划part17，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目1: 每日温度

• 题目链接：739. 每日温度

---

1- 思路

个人思路-暴力超时

• 暴力解法，双层 for 循环 根据外层的 i 通过 j 来遍历数组。
  • 如果当前 i小于 j 的元素，则记录 j-i。

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];// 双层 forfor(int i = 0; i < temperatures.length;i++){for(int j = i ; j < temperatures.length;j++){if( temperatures[j] > temperatures[i]){res[i] = j-i;break;}else if(j == temperatures.length-1){res[i] = 0;}}}return res;}
}

---

单调栈的意义

• 单调栈 可以帮你找出，数组中右边元素 第一个比当前元素大的元素是什么、或者找左边第一个比当前元素大的元素。

本题中单调栈的作用

• 本题中单调栈的作用是存放我们遍历过的元素
• 之前遍历过哪些元素，和当前元素作对比

本题单调栈中存储的值

• 如何存储，比较？
  • 直接存放下标
• 递增栈还是递减栈？
  • 递增 or 递减 指的是单调栈从栈口 到 栈底 的位置
  • 递增：求得是右边第一个比当前元素大的元素
  • 递减：求得是右边第一个比当前元素小的元素

思路

• 拿当前遍历到的元素 与 单调栈 的栈顶 元素做对比 ——> 根据三种情况进行判断，大于、小于、等于
• 当前元素 大于 栈顶元素：nums[i] > nums[st.peek()]，
  • 此时记录结果 res[st.peek()] = i - st.pop;
• 当前元素 小于 栈顶元素：
  • 此时当前元素入栈，所以保证的是一个单调递增的栈
• 当前元素 等于 栈顶元素：
  • 此时当前元素入栈

---

2- 题解

⭐ 每日温度 ——题解思路

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];// 定义单调栈Stack<Integer> st = new Stack();st.push(0);// 遍历 temperaturesfor(int i = 1 ; i < temperatures.length;i++){if(temperatures[i] <= temperatures[st.peek()]){st.push(i);}else{while(!st.isEmpty() && temperatures[i] > temperatures[st.peek()]){res[st.peek()] = i - st.peek();st.pop();}st.push(i);}}return res;}
}

---

题目2: 下一个更大元素 I

• 题目链接：496. 下一个更大元素 I

---

1- 思路

• 1- 定义 nums1 大小的结果集
• 2- 定义 Map 来寻找对应 nums2 中元素是否在 nums1 中
• 3- 遍历维持单调队列

---

2- 题解

⭐ 下一个更大元素 I——题解思路

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] res1 = new int[nums1.length];Arrays.fill(res1,-1);Stack<Integer> st = new Stack();st.push(0);// 针对 nums1 建立 MapMap<Integer,Integer> map = new HashMap<>();for(int i = 0 ; i < nums1.length;i++){map.put(nums1[i],i);}// 3- 维护 单调栈for(int i = 1 ; i < nums2.length;i++){if(nums2[i] <= nums2[st.peek()]){st.push(i);}else{while(!st.isEmpty() && nums2[i] > nums2[st.peek()]){if(map.containsKey(nums2[st.peek()])){int index = map.get(nums2[st.peek()]);res1[index] = nums2[i];}st.pop();}st.push(i);}}return res1;}
}

---

这篇关于【随想录】Day57—第九章 动态规划part17的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---