今天做算法題，遇到了這個題目，随後想把自己的想法寫出來。
題目是：
“曾經有兩次消除的機會擺在我面前，我卻沒有珍惜……”牛牛回憶道。
牛牛正在玩一款全新的消消樂遊戲。這款遊戲的主體是由一列列的方塊構成，牛牛的目标就是要盡量消除這些方塊。
每次操作，牛牛可以選擇某個高度 x，将所有高度大于等于 x 的那些列全部消除 x 個方塊，随後方塊會下落，以填補消除造成的空白。
牛牛這一局的發揮極佳，眼看就要破紀錄了，卻發現自己隻剩下了兩次消除機會。
為了不錯失這千載難逢的機會，他決定寫個程式來算出最優解。
簡明題意：
給定一個數組 nums，其中有 n 個非負整數。你的目的是進行兩次操作，使得數組的元素之和最小。
每次操作形如：任選一個整數 x ，将數組中所有大于等于 x 的數減去 x 。
示例1
輸入
[2, 1, 3]
輸出
說明
初始數組為 [2, 1, 3]。
先選擇 x = 2，則所有大于等于 2 的元素減去 2 ，變成 [0, 1, 1]。
再選擇 x = 1，則所有大于等于 1 的元素減去 1 ，變成 [0, 0, 0]。
是以數組元素之和的最小值為 0。
我的解法
import java.util.*;
public class Solution {
/**
* 傳回兩次操作後，數組元素之和的最小值
* @param nums int整型一維數組 這你你需要操作的數組
* @return long長整型
*/
public long minimumValueAfterDispel (int[] nums) {
// write code here
Arrays.sort(nums);
long sum = 0;//記錄整個數組的和
long max = 0;//記錄能夠減去的最大值
for(int j=0;j<nums.length;j++){
sum += nums[j];
int index1 = j;
int index2 = j;
int index3 = j;
for(int i=0;i<=j;i++){
while(index1 > 0 && nums[index1-1] >= nums[j]-nums[i]){
index1--;
}
while(index2 > i && nums[index2-1] >= nums[j]-nums[i]){
index2--;
}
while(index3 < nums.length && (long)nums[index3] < (long)nums[i]+nums[j]){
index3++;
}
/*
假設兩次減去的數為a,b(a<b)總共分為三種情況
1.a=nums[j]-nums[i] b=nums[i]
2.a=nums[i] b=nums[j]-nums[i]
3.a=nums[i] b=nums[j]
分段函數的邊界:
1. index1 < i < j < nums.length 其實index1大于i時不礙事 i-index1變成負數不會影響max的計算
2. i < index2 < j < nums.length
3. i < j < index3 < nums.length
對于第一種情況 index1到i之間的數隻能減去a 即 nums[j]-nums[i], i到j之間的數隻能減去b 即nums[i] , j到最後的數可以減去a+b 即nums[j]
對于第二種情況 i到index2之間的數隻能減去a 即 nums[i], index2到j之間的數隻能減去b 即nums[j]-nums[i] , j到最後的數可以減去a+b 即nums[j]
對于第三種情況 i到j之間的數隻能減去a 即 nums[i], j到index3之間的數隻能減去b 即nums[j], index3到最後的數可以減去a+b 即nums[j]+nums[i]
*/
long tmp1 = (i-index1)*((long)nums[j]-nums[i]) + (j-i)*(long)nums[i] + (nums.length-j)*(long)nums[j];
long tmp2 = (index2-i)*((long)nums[i]) + (j-index2)*((long)nums[j]-nums[i]) + (nums.length-j)*(long)nums[j];
long tmp3 = (j-i)*(long)nums[i] + (index3-j)*(long)nums[j] + (nums.length-index3)*((long)nums[i]+nums[j]);
max = Math.max(max,tmp1);
max = Math.max(max,tmp2);
max = Math.max(max,tmp3);
}
}
return sum - max;
}
}
大家有什麼好的解法也可以在評論區說出來
最後的最後，上點幹貨。（但凡有個這樣的女朋友，我會熬夜麼？）
最後我把我收集的各大廠經典高頻面試題和Java進階進階、架構師視訊教程送予大家。部分資料如下圖所示：
擷取位址：java進階學習資料，面試題，電子書籍免費擷取
