leetcode每日一题 2016. 增量元素之间的最大差值 简单模拟 一题三解两做

📖本篇内容：leetcode每日一题 2016. 增量元素之间的最大差值 简单模拟 一题三解两做~

📑 文章专栏：leetcode每日一题《打卡日常》

📆 最近更新：2022年2月25日 leetcode每日一题 537. 复数乘法 简单的字符串模拟拼接问题

🙊个人简介：一只二本院校在读的大三程序猿，本着注重基础，打卡算法，分享技术作为个人的经验总结性的博文博主，虽然可能有时会犯懒，但是还是会坚持下去的，如果你很喜欢博文的话，建议看下面一行~（疯狂暗示QwQ）

🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 _{关爱程序猿，从你我做起}

🙊写在前面🙊

今日早上在学校被冻醒了，说也是奇怪，昨天中午都被大太阳晒着都要出了汗，今天就冷的瑟瑟发抖，害，世事无常，大肠包小肠，不多说了，接着肝题啦~今天又是一道简单的模拟题，最近几天都是模拟，我怀疑过两天就是困难模拟题了！先不说了，今天这题一题三做。

题目

给你一个下标从 0 开始的整数数组 nums ，该数组的大小为 n ，请你计算 nums[j] - nums[i] 能求得的 最大差值 ，其中 0 <= i < j < n 且 nums[i] < nums[j] 。

返回 最大差值 。如果不存在满足要求的 i 和 j ，返回 -1 。

示例

示例1：

输入：nums = [7,1,5,4]
输出：4
解释：
最大差值出现在 i = 1 且 j = 2 时，nums[j] - nums[i] = 5 - 1 = 4 。
注意，尽管 i = 1 且 j = 0 时 ，nums[j] - nums[i] = 7 - 1 = 6 > 4 ，但 i > j 不满足题面要求，所以 6 不是有效的答案。

示例2:

输入：nums = [9,4,3,2]
输出：-1
解释：
不存在同时满足 i < j 和 nums[i] < nums[j] 这两个条件的 i, j 组合。

示例3：

输入：nums = [1,5,2,10]
输出：9
解释：
最大差值出现在 i = 0 且 j = 3 时，nums[j] - nums[i] = 10 - 1 = 9 。

提示

n == nums.length
2 <= n <= 1000
1 <= nums[i] <= 10^9

📝思路📝

本题考查知识点

• 思路1：简单的暴力模拟AC，直接一个双重for循环就可以搞定，但是这样的时间复杂度为 n^2，违背了咱们的算法思想初衷，所以咱们再来进行对应优化。
• 思路2: 尝试着优化为单次循环的思路 ， 优化为贪心的思路，由题咱们可以知道，i < j && nums[i] < nums[j],这样一来我们就可以假定判断当前所处位置时，最小的nums[i]的值即作为min，这样一来我们只需要计算当前所处位置的值 - 当前位置最小的nums[i] 的值就可以获取最大的差值了~
• 思路3：小付之前刷过剑指offer中的一道题——155. 最小栈 思路也可以参考最小栈，多维护一个辅助栈来进行求解答案数据，思路3和思路2本质相同，但是实现的情况有不同，这里可以进行参考。

⭐代码实现⭐

双重循环暴力AC

class Solution {public int maximumDifference(int[] nums) {int n = nums.length;int max = -1;for (int i = 0 ; i< n ; i++){for (int j = i+1;j<n;j++){// 进行判定 需要进行修改最大差值的前提如题所给if (max < nums[j] - nums[i] && nums[i] < nums[j])max = Math.max(nums[j] - nums[i],max);}}return max;}
}

单层循环贪心求解

class Solution {public int maximumDifference(int[] nums) {int n = nums.length;// 初始化没有找到的情况下的结果int max = -1;// 进行遍历 ，并且设置初始位置的最小nums[i] 为第一个元素for (int i = 0 ,min = nums[0]; i< n ;i++){// 如果满足 当前元素的值 大于了 当前所处位置的最小nums[i] 则进行更新我们的最大差值if (nums[i] > min) max = Math.max(nums[i] - min,max);// 更新我们 当前位置的最小nums[i] min = Math.min(min,nums[i]);}return max;}
}

辅助栈求解

class Solution {public int maximumDifference(int[] nums) {// 初始化辅助栈Stack<Integer> helpStack = new Stack<>();helpStack.push(nums[0]);// 初始化数据栈Stack<Integer> stack = new Stack<>();int max = -1;// 初始化for (int num : nums){stack.push(num);helpStack.push(Math.min(num,helpStack.peek()));}while (!stack.isEmpty() ){// 获取判断差值max = Math.max(stack.pop() - helpStack.pop(),max);}// 这步是为了防止i < j 时将其赋值引起的最小差值if (max == 0)return -1;return max;}
}

运行结果

双重循环暴力AC

单层循环 贪心求解

辅助栈求解

🙊写在最后🙊

2022-2-26今天小付打卡了哦~

美好的日出 美好的山河

都因有你存在 而璀璨 耀眼