maximum-score-of-a-good-subarray

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 an array of integers <code>nums</code> (0-indexed) and an integer <code>k</code>.

The score of a subarray <code>(i, j)</code> is defined as <code>min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)</code>. A good subarray is a subarray where <code>i &lt;= k &lt;= j</code>.

Return the maximum possible score of a good subarray.

&nbsp;
Example 1:

<pre>
Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15. 
</pre>

Example 2:

<pre>
Input: nums = [5,5,4,5,4,1,1,1], k = 0
Output: 20
Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= k &lt; nums.length</code></li>
</ul>

maximumScore

Maximum Score of a Good Subarray

Largest Rectangle in Histogram

largest-rectangle-in-histogram

柱状图中最大的矩形

Stack

Array

Two Pointers

Binary Search

Monotonic Stack

给你一个整数数组 <code>nums</code> （下标从 0 开始）和一个整数 <code>k</code> 。

一个子数组 <code>(i, j)</code> 的 分数 定义为 <code>min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)</code> 。一个 好 子数组的两个端点下标需要满足 <code>i &lt;= k &lt;= j</code> 。

请你返回 好 子数组的最大可能 分数 。

 

示例 1：

<pre>输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。
</pre>

示例 2：

<pre>输入：nums = [5,5,4,5,4,1,1,1], k = 0
输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= k &lt; nums.length</code></li>
</ul>