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

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

&＃x1f4d1; 文章专栏&＃xff1a;leetcode每日一题《打卡日常》

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

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

&＃x1f307; 点赞 &＃x1f44d; 收藏 ⭐留言 &＃x1f4dd; 一键三连 _{关爱程序猿&＃xff0c;从你我做起}

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

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

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

示例

示例1&＃xff1a;

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


示例2:

输入&＃xff1a;nums &＃61; [9,4,3,2]
输出&＃xff1a;-1
解释&＃xff1a;
不存在同时满足 i

示例3&＃xff1a;

输入&＃xff1a;nums &＃61; [1,5,2,10]
输出&＃xff1a;9
解释&＃xff1a;
最大差值出现在 i &＃61; 0 且 j &＃61; 3 时&＃xff0c;nums[j] - nums[i] &＃61; 10 - 1 &＃61; 9 。


提示

n &＃61;&＃61; nums.length
2 <&＃61; n <&＃61; 1000
1 <&＃61; nums[i] <&＃61; 10^9

&＃x1f4dd;思路&＃x1f4dd;

本题考查知识点

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