之前对题意理解有些偏差，认为找到最大值即可，但其实有的时候选择次大值作为peek才能找到最优解。
我的解法（错误）：
class Solution {
public long maximumSumOfHeights(List<Integer> maxHeights) {
int len = maxHeights.size();
int peek = 0;
List<Integer> p = new ArrayList<>();
for (int i = 0; i < len; ++i) {
if (maxHeights.get(i) > maxHeights.get(peek)) {
p.clear();
p.add(i);
peek = i;
} else if (maxHeights.get(i) == maxHeights.get(peek)) {
p.add(i);
peek = i;
}
}
long ans = 0L;
for (int pt = 0; pt < p.size(); ++pt) {
peek = p.get(pt);
long sum = 0L;
int lmin = maxHeights.get(peek), rmin = maxHeights.get(peek);
for (int i = peek; i >= 0; --i) {
lmin = Math.min(lmin, maxHeights.get(i));
sum += lmin;
}
for (int i = peek; i < len; ++i) {
rmin = Math.min(rmin, maxHeights.get(i));
sum += rmin;
}
ans = Math.max(ans, sum - maxHeights.get(peek));
}
return ans;
}
}
正确的做法应该是遍历每一个peek（即比左右两边大），然后判断最大和，应该是两重循环。
更简单的做法是单调栈（单调递减栈，即出栈顺序元素值递减）：
从右往左找到每个元素开始向右的一个递减序列最大和，
从左往右找到每个元素作为末尾的一个递增序列最大和。
参考视频：https://www.bilibili.com/video/BV1yu4y1z7sE/?p=87&spm_id_from=pageDriver 中的第三题
最标准的单调栈的思想就是：
遇到不符合的对象出栈，然后做一系列操作，最后加入当前元素。
while (!st.empty() && x <= a[st.peek()]) {
int j = st.pop();
...
}
st.push(i);
这道题入栈的是元素的下标值，‘一系列操作’指的是将原来添加进去的元素撤销（sum减掉原来的值），然后加入新的元素值，sum加上新的一堆值。
注意，我们设置了哨兵，所以suf数组的大小要设置为n+1，判断的时候也应该判断栈的长度是否大于1，而不是 是否为空。
另外，第二次找从左到右的递增序列时，就不需要设置数组了，直接使用一个值来存储，边存储边判断最大和就可以了。
class Solution {
public long maximumSumOfHeights(List<Integer> maxHeights) {
int[] a = maxHeights.stream().mapToInt(i -> i).toArray(); // 转化为int[]数组
int n = a.length;
long[] suf = new long[n + 1];
Stack<Integer> st = new Stack<>();
st.push(n); // 哨兵
long sum = 0;
for (int i = n - 1; i >= 0; --i) {
int x = a[i];
while (st.size() > 1 && x <= a[st.peek()]) {
int j = st.pop();
sum -= (long) a[j] * (st.peek() - j); // 撤销之前加到sum里的
}
sum += (long) x * (st.peek() - i); // 从 i 到 st.peek()-1 都是 x
suf[i] = sum;
st.push(i);
}
long ans = sum;
st.clear();
st.push(-1); // 哨兵
long pre = 0;
for (int i = 0; i < n; ++i) {
int x = a[i];
while (st.size() > 1 && x <= a[st.peek()]) {
int j = st.pop();
pre -= (long) a[j] * (j - st.peek()); // 撤销
}
pre += (long) x * (i - st.peek());
ans = Math.max(ans, pre + suf[i + 1]);
st.push(i);
}
return ans;
}
}
拓展：
long类型
long myLongVariable;
long myLongVariable = 1000000L;
- 在这行代码中，
maxHeights.stream().mapToInt(i -> i).toArray()执行了一系列操作：
maxHeights.stream(): 将maxHeights转换为一个流(Stream)。流是Java 8中引入的一种新的抽象，它允许对集合进行更加灵活和高效的操作。
mapToInt(i -> i): 调用了mapToInt方法，它会将每个元素映射为一个int值。在这个例子中，i -> i 是一个Lambda表达式，它表示对每个元素i，返回i本身。
toArray(): 将流(Stream)中的元素转换为一个数组。
综合起来，这行代码的作用是将maxHeights这个List中的元素转换为一个int数组。这个数组中的元素和maxHeights中的元素相同，只是数据结构从List转换为了数组。
