本文主要是介绍2866. 美丽塔 II（单调栈），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
之前对题意理解有些偏差，认为找到最大值即可，但其实有的时候选择次大值作为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 都是 xsuf[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转换为了数组。
这篇关于2866. 美丽塔 II（单调栈）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
