LeetCode算法心得——美丽塔 I（HashMap）

大家好，我是晴天学长，hashmap的灵活应用，然后边界的细节处理，需要的小伙伴可以关注支持一下哦！后续会继续更新的。

---

1) .美丽塔

---

美丽塔 I
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。

如果以下条件满足，我们称这些塔是 美丽 的：

1 <= heights[i] <= maxHeights[i]
heights 是一个 山状 数组。
如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山状 数组：

对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]
请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

示例 1：

输入：maxHeights = [5,3,4,1,1]
输出：13
解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]

• heights 是个山状数组，峰值在 i = 0 处。
  13 是所有美丽塔方案中的最大高度和。

示例 2：

输入：maxHeights = [6,5,3,9,2,7]
输出：22
解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：

• 1 <= heights[i] <= maxHeights[i]
• heights 是个山状数组，峰值在 i = 3 处。
  22 是所有美丽塔方案中的最大高度和。
  示例 3：

输入：maxHeights = [3,2,5,5,2,3]
输出：18
解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：

• 1 <= heights[i] <= maxHeights[i]
• heights 是个山状数组，最大值在 i = 2 处。
  注意，在这个方案中，i = 3 也是一个峰值。
  18 是所有美丽塔方案中的最大高度和。

提示：

1 <= n == maxHeights <= 103
1 <= maxHeights[i] <= 109

---

2) .算法思路

美丽塔 I
1.map存数值
2.取数值往两边遍历。
不能超过最大高度并且小于旁边新修的
3.注意越界

---

3) .算法步骤

1.创建一个HashMap（map）用于存储每个高度值对应的索引列表。这样可以将相同高度值的索引集中在一起。

2.遍历整数列表（maxHeights），将每个元素的索引添加到对应高度值的索引列表中。

3.遍历HashMap的键集合，获取每个高度值对应的索引列表。

4.对于每个高度值的索引列表，进行以下操作：
a. 初始化sumtemp为0，用于记录当前高度和。
b. 选择一个索引作为修塔的中心点（maxindex），并将该索引处的高度设为初始修塔高度。
c. 从中心点向左遍历，每次取当前高度和左侧高度的较小值作为修塔高度，并更新sumtemp。
d. 从中心点向右遍历，每次取当前高度和右侧高度的较小值作为修塔高度，并更新sumtemp。
e. 将sumtemp与当前最大高度和sum进行比较，更新sum的值为较大者。

5.返回最大高度和sum。

---

4）.代码示例

class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
         int max = 0;
            int maxindex = -1;
            long sum = 0;
            // 找最大位置(存下标, 相同的)
            Map<Integer, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < maxHeights.size(); i++) {
                int temp = maxHeights.get(i);
                    if (!map.containsKey(temp)){
                        map.put(temp, new ArrayList<>());
                    }
                    map.get(temp).add(i);
            }
            //遍历map
            for (int a: map.keySet()
                 ) {
                List<Integer> list = map.get(a);
                for (int j = 0; j < list.size(); j++) {
                    long sumtemp = 0;
                    maxindex = list.get(j);
                    //开始修塔
                    int[] nmus = new int[maxHeights.size()];
                    nmus[maxindex] = maxHeights.get(maxindex);
                    sumtemp+=maxHeights.get(maxindex);;
                    //左
                    int m = maxindex;
                    for (int i = maxindex; i >= 1; i--) {
                        if (i - 1 >= 0) {
                            int temp2 = Math.min(maxHeights.get(i-1), nmus[i]);
                            nmus[i-1] = temp2;
                            sumtemp += temp2;
                        }
                    }
                    //右
                    int n = maxindex;
                    for (int i = maxindex; i < maxHeights.size() - 1; i++) {
                        if (i + 1 < maxHeights.size()) {
                            int temp3 = Math.min(maxHeights.get(i+1), nmus[i]);
                            nmus[i + 1] = temp3;
                            sumtemp += temp3;
                        }
                    }
                    sum = Math.max(sumtemp,sum);
                }

            }
            //把最大值的小标提出了
            return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

---

5）.总结

• Hash的正确遍历。

---

试题链接：