nowcoder NC236题最大差值

迈不过友情╰ 2023-10-15 13:24 14阅读 0赞

**目录**

题目描述：

示例1

示例2

题干解析：

暴力求解：

代码展示：

优化：

代码展示：

--------------------

[题目跳转![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204?tpId=128&tqId=33768&ru=/exam/oj][icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_www.nowcoder.com_practice_a01abbdc52ba4d5f8777fb5dae91b204_tpId_128_tqId_33768_ru_exam_oj]

# 题目描述： #

有一个长为 n 的数组 A ，求满足 0 ≤ a ≤ b < n 的 A\[b\] - A\[a\] 的最大值。

给定数组 A 及它的大小 n ，请返回最大差值。

数据范围： ![2 < n \\leq 2 \* 10^\{5\}][2 _ n _leq 2 _ 10_5] ，数组中的值满足 ![0\\leq \\left | val \\right | \\leq 5 \* 10^\{8\}][0_leq _left _ val _right _ _leq 5 _ 10_8]

## 示例1 ##

> 输入：\[5,1\],2
> 
> 复制返回值：0

## 示例2 ##

> 输入：\[5,6\],2
> 
> 复制返回值：1

# 题干解析： #

从题目中我们可以**得出以下几点结论**：

1.  **从给定的 数组A 中求出****最大差值****；**
2.  **数组的顺序不能改变；**
3.  **结果必须****大于等于0****；**
4.  **必须是****后面的数****减****前面的数。**

## 暴力求解： ##

读完题目后我们可以很容易的写出暴力解法：

> **利用两个for()循环把每一个数都试一遍然后返回其中的最大值。**

### 代码展示： ###

public int getDis (int[] A, int n) {
    
            int max = 0;
            for (int i = 0; i < n; i++){
                for (int j = i+1; j < n; j++){
                    if (A[j] - A[i] > max){
                        max = A[j] - A[i];
                    }
                }
            }
     
            return max;
        }

**但是**当我们写完之后我们自己也一定会觉得**这段代码的时间复杂度太大了**可能会挂，运行之后也确实挂了。

![f8b55a8100054d98b52f1c87d5b66042.png][]

## 优化： ##

根据题目描述我们可以先简单的画一张折线图每一个点都是一个数据：

![9cba89131d1e4d52a94b82cfd97f7e11.png][]

![ef3a2ef6e1a745f0972bb85c512278a6.png][]

据图可知我们需要**返回**的是 **b1,b2,b3,b4,b5,b6 中的最大值** **。**

**此时我们我们就可以：**

1.  **定义一个 max 变量用来存储已遍历过的数最大差值；**
2.  **定义一个变量 a 用来存储已遍历过的数中的最小值；**
3.  **用一个 for()循环 来对 数组A 进行遍历，然后不断更新 max 和 a 的值。**

### 代码展示： ###

public int getDis (int[] A, int n) {
    
            int max = 0;
            int a = 0;
    
            for (int i = 1; i < n; i++){
                if (A[i] - A[a] > max){
                    max = A[i] - A[a];
                }
                if (A[i] < A[a]){
                    a = i;
                }
            }
    
            return max;
        }

此时代码的**时间复杂度被压缩到了O(n)**，所以只要思路正确就一定会通过。

![15f3c3cb01264824af7830369ae16e18.png][]

[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_www.nowcoder.com_practice_a01abbdc52ba4d5f8777fb5dae91b204_tpId_128_tqId_33768_ru_exam_oj]: https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204?tpId=128&tqId=33768&ru=/exam/oj
[2 _ n _leq 2 _ 10_5]: https://latex.csdn.net/eq?2%20%3C%20n%20%5Cleq%202%20*%2010%5E%7B5%7D
[0_leq _left _ val _right _ _leq 5 _ 10_8]: https://latex.csdn.net/eq?0%5Cleq%20%5Cleft%20%7C%20val%20%5Cright%20%7C%20%5Cleq%205%20*%2010%5E%7B8%7D
[f8b55a8100054d98b52f1c87d5b66042.png]: https://img-blog.csdnimg.cn/f8b55a8100054d98b52f1c87d5b66042.png
[9cba89131d1e4d52a94b82cfd97f7e11.png]: https://img-blog.csdnimg.cn/9cba89131d1e4d52a94b82cfd97f7e11.png
[ef3a2ef6e1a745f0972bb85c512278a6.png]: https://img-blog.csdnimg.cn/ef3a2ef6e1a745f0972bb85c512278a6.png
[15f3c3cb01264824af7830369ae16e18.png]: https://img-blog.csdnimg.cn/15f3c3cb01264824af7830369ae16e18.png