maximum-balanced-shipments

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Use a monotonic stack to find for each end index <code>i</code> the nearest previous index <code>j</code> with <code>weight[j] > weight[i]</code> (set <code>j = -1</code> if none).

Then set <code>dp[i] = best[j] + 1</code> (using <code>best[-1] = 0</code>), and update <code>best[i] = max(best[i-1], dp[i])</code>; the result is <code>best[n-1]</code>.

Algorithms

You are given an integer array <code data-end="62" data-start="54">weight</code> of length <code data-end="76" data-start="73">n</code>, representing the weights of <code data-end="109" data-start="106">n</code> parcels arranged in a straight line. A shipment is defined as a contiguous subarray of parcels. A shipment is considered balanced if the weight of the last parcel is strictly less than the maximum weight among all parcels in that shipment.

Select a set of non-overlapping, contiguous, balanced shipments such that each parcel appears in at most one shipment (parcels may remain unshipped).

Return the maximum possible number of balanced shipments that can be formed.

&nbsp;
Example 1:

<div class="example-block">
Input: weight = [2,5,1,4,3]

Output: 2

Explanation:

We can form the maximum of two balanced shipments as follows:

<ul>
	<li data-end="163" data-start="140">Shipment 1: <code>[2, 5, 1]</code>

	<ul>
		<li data-end="195" data-start="168">Maximum parcel weight = 5</li>
		<li data-end="275" data-start="200">Last parcel weight = 1, which is strictly less than 5. Thus, it&#39;s balanced.</li>
	</ul>
	</li>
	<li data-end="299" data-start="279">Shipment 2: <code>[4, 3]</code>
	<ul>
		<li data-end="331" data-start="304">Maximum parcel weight = 4</li>
		<li data-end="411" data-start="336">Last parcel weight = 3, which is strictly less than 4. Thus, it&#39;s balanced.</li>
	</ul>
	</li>
</ul>

It is impossible to partition the parcels to achieve more than two balanced shipments, so the answer is 2.
</div>

Example 2:

<div class="example-block">
Input: weight = [4,4]

Output: 0

Explanation:

No balanced shipment can be formed in this case:

<ul>
	<li data-end="772" data-start="639">A shipment <code>[4, 4]</code> has maximum weight 4 and the last parcel&#39;s weight is also 4, which is not strictly less. Thus, it&#39;s not balanced.</li>
	<li data-end="885" data-start="775">Single-parcel shipments <code>[4]</code> have the last parcel weight equal to the maximum parcel weight, thus not balanced.</li>
</ul>

As there is no way to form even one balanced shipment, the answer is 0.
</div>

&nbsp;
Constraints:

<ul>
	<li data-end="8706" data-start="8671"><code data-end="8704" data-start="8671">2 &lt;= n &lt;= 105</code></li>
	<li data-end="8733" data-start="8709"><code data-end="8733" data-start="8709">1 &lt;= weight[i] &lt;= 109</code></li>
</ul>

第 461 场周赛

weekly-contest-461

maxBalancedShipments

资深工程师

Maximum Balanced Shipments

Stack

Greedy

Array

Dynamic Programming

Monotonic Stack

给你一个长度为 <code data-end="76" data-start="73">n</code> 的整数数组 <code data-end="62" data-start="54">weight</code>，表示按直线排列的 <code data-end="109" data-start="106">n</code> 个包裹的重量。装运&nbsp;定义为包裹的一个连续子数组。如果一个装运满足以下条件，则称其为 平衡装运：最后一个包裹的重量 严格小于&nbsp;该装运中所有包裹中&nbsp;最大重量&nbsp;。

选择若干个&nbsp;不重叠&nbsp;的连续平衡装运，并满足&nbsp;每个包裹最多出现在一次装运中（部分包裹可以不被装运）。

返回 可以形成的平衡装运的最大数量&nbsp;。

&nbsp;

示例 1:

<div class="example-block">
输入: weight = [2,5,1,4,3]

输出: 2

解释:

我们可以形成最多两个平衡装运：

<ul>
	<li data-end="163" data-start="140">装运 1: <code>[2, 5, 1]</code>

	<ul>
		<li data-end="195" data-start="168">包裹的最大重量 = 5</li>
		<li data-end="275" data-start="200">最后一个包裹的重量 = 1，严格小于 5，因此这是平衡装运。</li>
	</ul>
	</li>
	<li data-end="299" data-start="279">装运 2: <code>[4, 3]</code>
	<ul>
		<li data-end="331" data-start="304">包裹的最大重量 = 4</li>
		<li data-end="411" data-start="336">最后一个包裹的重量 = 3，严格小于 4，因此这是平衡装运。</li>
	</ul>
	</li>
</ul>

无法通过其他方式划分包裹获得超过两个平衡装运，因此答案是 2。
</div>

示例 2:

<div class="example-block">
输入: weight = [4,4]

输出: 0

解释:

在这种情况下无法形成平衡装运：

<ul>
	<li data-end="772" data-start="639">装运 <code>[4, 4]</code> 的最大重量为 4，而最后一个包裹的重量也是 4，不严格小于最大重量，因此不是平衡的。</li>
	<li data-end="885" data-start="775">单个包裹的装运 <code>[4]</code> 中，最后一个包裹的重量等于最大重量，因此也不是平衡的。</li>
</ul>

由于无法形成任何平衡装运，答案是 0。
</div>

&nbsp;

提示:

<ul>
	<li data-end="8706" data-start="8671"><code data-end="8704" data-start="8671">2 &lt;= n &lt;= 105</code></li>
	<li data-end="8733" data-start="8709"><code data-end="8733" data-start="8709">1 &lt;= weight[i] &lt;= 109</code></li>
</ul>

平衡装运的最大数量

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给你一个长度为 n 的整数数组 weight，表示按直线排列的 n 个包裹的重量。装运 定义为包裹的一个连续子数组。如果一个装运满足以下条件，则称其为 平衡装运：最后一个包裹的重量 严格小于 该装运中所有包裹中 最大重量 。

选择若干个 不重叠 的连续平衡装运，并满足 每个包裹最多出现在一次装运中（部分包裹可以不被装运）。

返回 可以形成的平衡装运的最大数量 。

 

示例 1:

输入: weight = [2,5,1,4,3]

输出: 2

解释:

我们可以形成最多两个平衡装运：

 * 装运 1: [2, 5, 1]
 * 包裹的最大重量 = 5
 * 最后一个包裹的重量 = 1，严格小于 5，因此这是平衡装运。
 * 装运 2: [4, 3]
 * 包裹的最大重量 = 4
 * 最后一个包裹的重量 = 3，严格小于 4，因此这是平衡装运。

无法通过其他方式划分包裹获得超过两个平衡装运，因此答案是 2。

示例 2:

输入: weight = [4,4]

输出: 0

解释:

在这种情况下无法形成平衡装运：

 * 装运 [4, 4] 的最大重量为 4，而最后一个包裹的重量也是 4，不严格小于最大重量，因此不是平衡的。
 * 单个包裹的装运 [4] 中，最后一个包裹的重量等于最大重量，因此也不是平衡的。

由于无法形成任何平衡装运，答案是 0。

 

提示:

 * 2 <= n <= 105
 * 1 <= weight[i] <= 109