3301. Maximize the Total Height of Unique Towers
You are given an array maximumHeight, where maximumHeight[i] denotes the maximum height the ith tower can be assigned.
Your task is to assign a height to each tower so that:
- The height of the
ithtower is a positive integer and does not exceedmaximumHeight[i]. - No two towers have the same height.
Return the maximum possible total sum of the tower heights. If it's not possible to assign heights, return -1.
Example 1:
Input: maximumHeight = [2,3,4,3]
Output: 10
Explanation:
We can assign heights in the following way: [1, 2, 4, 3].
Example 2:
Input: maximumHeight = [15,10]
Output: 25
Explanation:
We can assign heights in the following way: [15, 10].
Example 3:
Input: maximumHeight = [2,2,1]
Output: -1
Explanation:
It's impossible to assign positive heights to each index so that no two towers have the same height.
Constraints:
1 <= maximumHeight.length <= 1051 <= maximumHeight[i] <= 109
Solution:
class Solution {
public long maximumTotalSum(int[] maximumHeight) {
/*
2 3 4 3
i
*/
Set<Integer> set = new HashSet<Integer>();
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> (b - a));
for (int i = 0; i < maximumHeight.length; i++){
pq.offer(maximumHeight[i]);
}
int count = maximumHeight.length;//
int result = 0;
while(count > 0){
int cur = pq.poll();//2
while(set.contains(cur)){//1
cur = cur - 1;
}
if (cur == 0){
return -1;
}
result = result + cur;//2+1=3
set.add(cur);//2
count--;//1
}
return (long) result;
}
}
// 548 / 583 testcases passed
// [440467371,363047937,396752573,153156429,453056479,484430768,72480750,17339965,346744441,315056705,494127292,480524965,21471248,497944920,324943422,288419091,296229725,284598403,282343852,365397216,34953386,111202289,223048853,117280101,353859720,205061780,488961679,158878756,182521649,347518438,71555589,214669060,146099226,441573395,191712055,51293602,83568928,230389286,23250253,98913575,239868399,415687876,5787205,65101961,23995465,60017337,379395070,30472617,440430814,262460178,391589109,177788146,308640915,362720426,395830974,256503135,466967299,241495473,182737979,148117879,107139612,378198772,74523193,5177463,408137660,352387747,109171944,39575012,38870063,145677210,401295338,364988468,201501118,237331598,26820292,432504189,158224392,428794826,166198683,91066138,86288288,235705633,190870948,435662963,30340851,115529036,401869840,65789185,26346380,41044580,366991310,84558408,7118456,78280176,135391010,3995579,389545417,490785565,372454095,464029197,31352312,323126493,199408614,88424724,95442478,130268884,69962436,295596776,471704688,248832317,363424637,239603974,44723346,372426536,368192981,219453297,19473139,34315559,241659506,436892925,500089668,293420280,252880647,116009707,228834118,162639840,403000423,377946752,499100182,69150611,432685090,222382089,312539785,94155030,429913752,276003646,255777939,12990088,282003863,500572721,428110740,212067860,463043886,119203650,156173208,82217388,406910864,296837448,461209207,198553391,245396791,459401659,170644979,397093227,16256569,458507260,401890702,443343331,41679194,53974187,421745115,388456113,238949551,381817668,371385589,416212611,119634728,221047435,35300523,345659623,331807790,21124946,424504606,279577435,171041845,362792281,125356186,377308988,382506765,82903595,212576695,280441244,55755282,97616679,268102262,240501561,263068503,399216854,367318286,937176,304251223,8431431,408797601,3749232,3748921,76325863,296062525,106334670,147081020,287409502,479497962,426172630,381949438,190426889,370644790,126801198,123649083,290299226,29124713,294554198,352191317,33231178,359594101,112453112,286707621,226978161,50230527,96227539,364236835,22756823,459254343,205042306,68861165,214434979,3754628,280972341,256836845,88325030,72590962,282396746,213981824,457867663,313863008,310722001,40331209,26944141]
// 精度问题
class Solution {
public long maximumTotalSum(int[] maximumHeight) {
/*
2 3 4 3
i
*/
Set<Integer> set = new HashSet<Integer>();
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> (b - a));
for (int i = 0; i < maximumHeight.length; i++){
pq.offer(maximumHeight[i]);
}
int count = maximumHeight.length;//
long result = 0; //
while(count > 0){
int cur = pq.poll();//2
while(set.contains(cur)){//1
cur = cur - 1;
}
if (cur == 0){
return -1;
}
result = result + cur;//2+1=3
set.add(cur);//2
count--;//1
}
return result;
}
}
// 573 / 583 testcases passed
// Time Limit Exceeded
// TC: O(nlogn)
// SC: O(n)
class Solution {
public long maximumTotalSum(int[] maximumHeight) {
/*
2 3 4 3
i
*/
// Arrays.sort(maximumHeight);
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> (b - a));
for (int i = 0; i < maximumHeight.length; i++){
pq.offer(maximumHeight[i]);
}
long result = 0;
int currentHeight = Integer.MAX_VALUE;
while(!pq.isEmpty()){
int cur = pq.poll();
cur = Math.min(cur, currentHeight - 1);
if (cur <= 0){
return -1;
}
result = cur + result;
currentHeight = cur;
}
return result;
}
}
// 优化思路
// 直接使用 PriorityQueue: 在每次从 PriorityQueue 中取出元素时，确保当前的高度比上一次使用的高度小。这可以通过一个简单的 currentHeight 变量来实现。
//避免重复检查: 在处理 PriorityQueue 时，始终确保新选的高度小于上一次的高度，避免重复。
class Solution {
public long maximumTotalSum(int[] maximumHeight) {
// Sort the array in ascending order
Arrays.sort(maximumHeight);
long totalSum = 0;
int currentHeight = Integer.MAX_VALUE;
// Traverse from the highest value to the lowest value
for (int i = maximumHeight.length - 1; i >= 0; i--) {
// Assign the largest possible unique height
currentHeight = Math.min(currentHeight - 1, maximumHeight[i]);
// If we can't assign a valid positive height, return -1
if (currentHeight <= 0) {
return -1;
}
// Add the height to the total sum
totalSum += currentHeight;
}
return totalSum;
}
}