sliding-subarray-beauty

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an integer array <code>nums</code> containing <code>n</code> integers, find the beauty of each subarray of size <code>k</code>.

The beauty of a subarray is the <code>xth</code> smallest integer in the subarray if it is negative, or <code>0</code> if there are fewer than <code>x</code> negative integers.

Return an integer array containing <code>n - k + 1</code> integers, which denote the beauty of the subarrays in order from the first index in the array.

<ul>
	<li>
	A subarray is a contiguous non-empty sequence of elements within an array.
	</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: nums = [1,-1,-3,-2,3], k = 3, x = 2
Output: [-1,-2,-2]
Explanation: There are 3 subarrays with size k = 3. 
The first subarray is <code>[1, -1, -3]</code> and the 2nd smallest negative integer is -1.&nbsp;
The second subarray is <code>[-1, -3, -2]</code> and the 2nd smallest negative integer is -2.&nbsp;
The third subarray is <code>[-3, -2, 3]&nbsp;</code>and the 2nd smallest negative integer is -2.</pre>

Example 2:

<pre>
Input: nums = [-1,-2,-3,-4,-5], k = 2, x = 2
Output: [-1,-2,-3,-4]
Explanation: There are 4 subarrays with size k = 2.
For <code>[-1, -2]</code>, the 2nd smallest negative integer is -1.
For <code>[-2, -3]</code>, the 2nd smallest negative integer is -2.
For <code>[-3, -4]</code>, the 2nd smallest negative integer is -3.
For <code>[-4, -5]</code>, the 2nd smallest negative integer is -4.&nbsp;</pre>

Example 3:

<pre>
Input: nums = [-3,1,2,-3,0,-3], k = 2, x = 1
Output: [-3,0,-3,-3,-3]
Explanation: There are 5 subarrays with size k = 2.
For <code>[-3, 1]</code>, the 1st smallest negative integer is -3.
For <code>[1, 2]</code>, there is no negative integer so the beauty is 0.
For <code>[2, -3]</code>, the 1st smallest negative integer is -3.
For <code>[-3, 0]</code>, the 1st smallest negative integer is -3.
For <code>[0, -3]</code>, the 1st smallest negative integer is -3.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums.length&nbsp;</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
	<li><code>1 &lt;= x &lt;= k&nbsp;</code></li>
	<li><code>-50&nbsp;&lt;= nums[i] &lt;= 50&nbsp;</code></li>
</ul>

getSubarrayBeauty

Sliding Subarray Beauty

Array

Hash Table

Sliding Window

给你一个长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;，请你求出每个长度为&nbsp;<code>k</code>&nbsp;的子数组的 美丽值&nbsp;。

一个子数组的 美丽值&nbsp;定义为：如果子数组中第 <code>x</code>&nbsp;小整数&nbsp;是 负数&nbsp;，那么美丽值为第 <code>x</code>&nbsp;小的数，否则美丽值为 <code>0</code>&nbsp;。

请你返回一个包含&nbsp;<code>n - k + 1</code>&nbsp;个整数的数组，依次&nbsp;表示数组中从第一个下标开始，每个长度为&nbsp;<code>k</code>&nbsp;的子数组的&nbsp;美丽值&nbsp;。

<ul>
	<li>
	子数组指的是数组中一段连续 非空&nbsp;的元素序列。
	</li>
</ul>

&nbsp;

示例 1：

<pre>输入：nums = [1,-1,-3,-2,3], k = 3, x = 2
输出：[-1,-2,-2]
解释：总共有 3 个 k = 3 的子数组。
第一个子数组是 <code>[1, -1, -3]</code> ，第二小的数是负数 -1 。
第二个子数组是 <code>[-1, -3, -2]</code> ，第二小的数是负数 -2 。
第三个子数组是 <code>[-3, -2, 3]&nbsp;，第二小的数是负数 -2 。</code></pre>

示例 2：

<pre>输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
<code>[-1, -2] 中第二小的数是负数 -1 。</code>
<code>[-2, -3] 中第二小的数是负数 -2 。</code>
<code>[-3, -4] 中第二小的数是负数 -3 。</code>
<code>[-4, -5] 中第二小的数是负数 -4 。</code></pre>

示例 3：

<pre>输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
<code>[-3, 1] 中最小的数是负数 -3 。</code>
<code>[1, 2] 中最小的数不是负数，所以美丽值为 0 。</code>
<code>[2, -3] 中最小的数是负数 -3 。</code>
<code>[-3, 0] 中最小的数是负数 -3 。</code>
<code>[0, -3] 中最小的数是负数 -3 。</code></pre>

&nbsp;

提示：

<ul>
	<li><code>n == nums.length&nbsp;</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
	<li><code>1 &lt;= x &lt;= k&nbsp;</code></li>
	<li><code>-50&nbsp;&lt;= nums[i] &lt;= 50&nbsp;</code></li>
</ul>