东阳市建设局网站,平泉建设局网站,互联壹佰做企业网站,辽宁省建设工程题面 给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i #xff0c;高度为 heights[i] 。
如果以下条件满足#xff0c;我们称这些塔是 美丽 的#xff1a;
1 heights[i] maxHeights[i] heights 是… 题面 给你一个长度为 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] 请你返回满足 美丽塔 要求的方案中高度和的最大值 。 思路 题面有点像合唱队列那道题。
状态方程 f [ i ] { f [ i − 1 ] h [ i ] h [ i ] ≥ h [ i − 1 ] f [ j ] ( i − j ) ∗ h [ i ] h [ i ] h [ i − 1 ] \begin{equation} f[i] \begin{cases} f[i-1]h[i] h[i]\ge h[i-1]\\ f[j](i-j)*h[i] h[i] h[i-1] \end{cases} \end{equation} f[i]{f[i−1]h[i]f[j](i−j)∗h[i]h[i]≥h[i−1]h[i]h[i−1] f[i]为前i个满足题意的最大值j为当前i从左往右第一个小于或等于的下标(单调栈维护)同理右边g[i]也可以得出结果为max(f[i]g[i]-h[i])。 代码 public long maximumSumOfHeights(ListInteger maxHeights) {int n maxHeights.size();int[] left new int[n 1];int[] right new int[n 1];Arrays.fill(left, -1);Arrays.fill(right, n);DequeInteger deque new ArrayDeque();for (int i 0; i n; i) {int x maxHeights.get(i);while (!deque.isEmpty() x maxHeights.get(deque.peek())) {deque.pop();}if (!deque.isEmpty()) {left[i] deque.peek();}deque.push(i);}deque.clear();for (int i n - 1; i 0; i--) {int x maxHeights.get(i);while (!deque.isEmpty() x maxHeights.get(deque.peek())) {deque.pop();}if (!deque.isEmpty()) {right[i] deque.peek();}deque.push(i);}long[] f new long[n];long[] g new long[n];for (int i 0; i n; i) {int x maxHeights.get(i);if (i 0 x maxHeights.get(i - 1)) {f[i] f[i - 1] x;} else {int j left[i];f[i] (long) x * (i - j) (j 0 ? f[j] : 0);}}for (int i n - 1; i 0; i--) {int x maxHeights.get(i);if (i n - 1 x maxHeights.get(i 1)) {g[i] g[i 1] x;} else {int j right[i];g[i] (long) x * (j - i) (j n ? g[j] : 0);}}long ans 0;for (int i 0; i n; i) {ans Math.max(ans, f[i] g[i] - maxHeights.get(i));}return ans;
}说明 为什么左边是小于等于右边计算时是小于见下图应该就懂了
