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

单层循环贪心求解

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 helpStack = new Stack<>(); helpStack.push(nums[0]); // 初始化数据栈 Stack 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今天小付打卡了哦~

美好的日出 美好的山河

都因有你存在 而璀璨 耀眼