beautiful-towers-ii

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed array <code>maxHeights</code> of <code>n</code> integers.

You are tasked with building <code>n</code> towers in the coordinate line. The <code>ith</code> tower is built at coordinate <code>i</code> and has a height of <code>heights[i]</code>.

A configuration of towers is beautiful if the following conditions hold:

<ol>
	<li><code>1 &lt;= heights[i] &lt;= maxHeights[i]</code></li>
	<li><code>heights</code> is a mountain array.</li>
</ol>

Array <code>heights</code> is a mountain if there exists an index <code>i</code> such that:

<ul>
	<li>For all <code>0 &lt; j &lt;= i</code>, <code>heights[j - 1] &lt;= heights[j]</code></li>
	<li>For all <code>i &lt;= k &lt; n - 1</code>, <code>heights[k + 1] &lt;= heights[k]</code></li>
</ul>

Return the maximum possible sum of heights of a beautiful configuration of towers.

&nbsp;
Example 1:

<pre>
Input: maxHeights = [5,3,4,1,1]
Output: 13
Explanation: One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
- 1 &lt;= heights[i] &lt;= maxHeights[i] 
- heights is a mountain of peak i = 0.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.</pre>

Example 2:

<pre>
Input: maxHeights = [6,5,3,9,2,7]
Output: 22
Explanation: One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
- 1 &lt;= heights[i] &lt;= maxHeights[i]
- heights is a mountain of peak i = 3.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.</pre>

Example 3:

<pre>
Input: maxHeights = [3,2,5,5,2,3]
Output: 18
Explanation: One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
- 1 &lt;= heights[i] &lt;= maxHeights[i]
- heights is a mountain of peak i = 2. 
Note that, for this configuration, i = 3 can also be considered a peak.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == maxHeights.length &lt;= 105</code></li>
	<li><code>1 &lt;= maxHeights[i] &lt;= 109</code></li>
</ul>

maximumSumOfHeights

Beautiful Towers II

Minimum Number of Removals to Make Mountain Array

minimum-number-of-removals-to-make-mountain-array

得到山形数组的最少删除次数

Maximum Number of Books You Can Take

maximum-number-of-books-you-can-take

你能拿走的最大图书数量

Stack

Array

Monotonic Stack

给你一个长度为 <code>n</code>&nbsp;下标从 0&nbsp;开始的整数数组&nbsp;<code>maxHeights</code>&nbsp;。

你的任务是在坐标轴上建 <code>n</code>&nbsp;座塔。第&nbsp;<code>i</code>&nbsp;座塔的下标为 <code>i</code>&nbsp;，高度为&nbsp;<code>heights[i]</code>&nbsp;。

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

<ol>
	<li><code>1 &lt;= heights[i] &lt;= maxHeights[i]</code></li>
	<li><code>heights</code>&nbsp;是一个 山脉 数组。</li>
</ol>

如果存在下标 <code>i</code>&nbsp;满足以下条件，那么我们称数组&nbsp;<code>heights</code>&nbsp;是一个 山脉 数组：

<ul>
	<li>对于所有&nbsp;<code>0 &lt; j &lt;= i</code>&nbsp;，都有&nbsp;<code>heights[j - 1] &lt;= heights[j]</code></li>
	<li>对于所有&nbsp;<code>i &lt;= k &lt; n - 1</code>&nbsp;，都有&nbsp;<code>heights[k + 1] &lt;= heights[k]</code></li>
</ul>

请你返回满足 美丽塔&nbsp;要求的方案中，高度和的最大值&nbsp;。

&nbsp;

示例 1：

<pre>
输入：maxHeights = [5,3,4,1,1]
输出：13
解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
- 1 &lt;= heights[i] &lt;= maxHeights[i] 
- heights 是个山脉数组，峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。</pre>

示例 2：

<pre>
输入：maxHeights = [6,5,3,9,2,7]
输出：22
解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：
- 1 &lt;= heights[i] &lt;= maxHeights[i]
- heights 是个山脉数组，峰值在 i = 3 处。
22 是所有美丽塔方案中的最大高度和。</pre>

示例 3：

<pre>
输入：maxHeights = [3,2,5,5,2,3]
输出：18
解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：
- 1 &lt;= heights[i] &lt;= maxHeights[i]
- heights 是个山脉数组，最大值在 i = 2 处。
注意，在这个方案中，i = 3 也是一个峰值。
18 是所有美丽塔方案中的最大高度和。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n == maxHeights&nbsp;&lt;= 105</code></li>
	<li><code>1 &lt;= maxHeights[i] &lt;= 109</code></li>
</ul>