要做这道题目呢,首先需要知道差分数组的概念。还没有了解过的同学需要先去了解一下噢。
知道差分数组的概念后,我们开始想这道题,我们使得区间[L,R]之内的所有积木的高度加1,对于差分数组del来说呢就是使得del[L]+1,del[R+1]-1。
那么我们每一次操作都会使得差分数组中的两个元素发生变化,一个加一,一个减一。那么整个差分数组的和实际上是0。根据这个我们实际上就可以通过差分数组中所有正数的和次数的操作,让差分数组变为全0的状态。然后就能得出我们的解法啦。
Java 代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] h = new int[n];//原高度数组
for(int i = 0 ; i < n ; i++){
h[i] = input.nextInt();
}
int res = 0;
for(int i = n-1;i >= 0 ; i--){
if(i == 0){
res += h[0];
}else{
res += h[i] - h[i-1] > 0 ? h[i] - h[i-1] : 0;
}
}
System.out.println(res);
}
}