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

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>