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今天小付打卡了哦~
 
美好的日出 美好的山河
 
都因有你存在 而璀璨 耀眼