Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit741bea8

Browse files
authored
feat: add solutions to lc problem: No.3555 (#4417)
No.3555.Smallest Subarray to Sort in Every Sliding Window
1 parent81ba6c0 commit741bea8

File tree

7 files changed

+454
-8
lines changed

7 files changed

+454
-8
lines changed

‎solution/3500-3599/3555.Smallest Subarray to Sort in Every Sliding Window/README.md

Lines changed: 155 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -69,32 +69,183 @@ edit_url: https://github.com/doocs/leetcode/edit/main/solution/3500-3599/3555.Sm
6969

7070
<!-- solution:start-->
7171

72-
###方法一
72+
###方法一：枚举 + 维护左侧最大值和右侧最小值
73+
74+
我们可以枚举每个长度为 $k$ 的子数组，对于每个子数组 $nums[i...i + k - 1]$，我们需要找到最小的连续段，使得排序后整个子数组都是非递减的。
75+
76+
对于子数组 $nums[i...i + k - 1]$，我们可以从左到右遍历数组，维护一个最大值 $mx$，如果当前值小于 $mx$，说明当前值不在正确的位置上，我们更新右边界 $r$ 为当前位置。同理，我们可以从右到左遍历数组，维护一个最小值 $mi$，如果当前值大于 $mi$，说明当前值不在正确的位置上，我们更新左边界 $l$ 为当前位置。在初始化时，我们将 $l$ 和 $r$ 都初始化为 $-1$，如果 $l$ 和 $r$ 都没有被更新，说明数组已经有序，返回 $0$，否则返回 $r - l + 1$。
77+
78+
时间复杂度 $O(n \times k)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。
7379

7480
<!-- tabs:start-->
7581

7682
####Python3
7783

7884
```python
79-
85+
classSolution:
86+
defminSubarraySort(self,nums: List[int],k:int) -> List[int]:
87+
deff(i:int,j:int) ->int:
88+
mi, mx= inf,-inf
89+
l= r=-1
90+
for kinrange(i, j+1):
91+
if mx> nums[k]:
92+
r= k
93+
else:
94+
mx= nums[k]
95+
p= j- k+ i
96+
if mi< nums[p]:
97+
l= p
98+
else:
99+
mi= nums[p]
100+
return0if r==-1else r- l+1
101+
102+
n=len(nums)
103+
return [f(i, i+ k-1)for iinrange(n- k+1)]
80104
```
81105

82106
####Java
83107

84108
```java
85-
109+
classSolution {
110+
privateint[] nums;
111+
privatefinalint inf=1<<30;
112+
113+
publicint[]minSubarraySort(int[]nums,intk) {
114+
this.nums= nums;
115+
int n= nums.length;
116+
int[] ans=newint[n- k+1];
117+
for (int i=0; i< n- k+1;++i) {
118+
ans[i]= f(i, i+ k-1);
119+
}
120+
return ans;
121+
}
122+
123+
privateintf(inti,intj) {
124+
int mi= inf, mx=-inf;
125+
int l=-1, r=-1;
126+
for (int k= i; k<= j;++k) {
127+
if (nums[k]< mx) {
128+
r= k;
129+
}else {
130+
mx= nums[k];
131+
}
132+
int p= j- k+ i;
133+
if (nums[p]> mi) {
134+
l= p;
135+
}else {
136+
mi= nums[p];
137+
}
138+
}
139+
return r==-1?0: r- l+1;
140+
}
141+
}
86142
```
87143

88144
####C++
89145

90146
```cpp
91-
147+
classSolution {
148+
public:
149+
vector<int> minSubarraySort(vector<int>& nums, int k) {
150+
const int inf = 1 << 30;
151+
int n = nums.size();
152+
auto f =[&](int i, int j) -> int {
153+
int mi = inf, mx = -inf;
154+
int l = -1, r = -1;
155+
for (int k = i; k <= j; ++k) {
156+
if (nums[k] < mx) {
157+
r = k;
158+
} else {
159+
mx = nums[k];
160+
}
161+
int p = j - k + i;
162+
if (nums[p] > mi) {
163+
l = p;
164+
} else {
165+
mi = nums[p];
166+
}
167+
}
168+
return r == -1 ? 0 : r - l + 1;
169+
};
170+
vector<int> ans;
171+
for (int i = 0; i < n - k + 1; ++i) {
172+
ans.push_back(f(i, i + k - 1));
173+
}
174+
return ans;
175+
}
176+
};
92177
```
93178
94179
#### Go
95180
96181
```go
182+
func minSubarraySort(nums []int, k int) []int {
183+
const inf = 1 << 30
184+
n := len(nums)
185+
f := func(i, j int) int {
186+
mi := inf
187+
mx := -inf
188+
l, r := -1, -1
189+
for p := i; p <= j; p++ {
190+
if nums[p] < mx {
191+
r = p
192+
} else {
193+
mx = nums[p]
194+
}
195+
q := j - p + i
196+
if nums[q] > mi {
197+
l = q
198+
} else {
199+
mi = nums[q]
200+
}
201+
}
202+
if r == -1 {
203+
return 0
204+
}
205+
return r - l + 1
206+
}
207+
208+
ans := make([]int, 0, n-k+1)
209+
for i := 0; i <= n-k; i++ {
210+
ans = append(ans, f(i, i+k-1))
211+
}
212+
return ans
213+
}
214+
```
97215

216+
####TypeScript
217+
218+
```ts
219+
function minSubarraySort(nums:number[],k:number):number[] {
220+
const inf=Infinity;
221+
const n=nums.length;
222+
const f= (i:number,j:number):number=> {
223+
let mi=inf;
224+
let mx=-inf;
225+
let l=-1,
226+
r=-1;
227+
for (let p=i;p<=j;++p) {
228+
if (nums[p]<mx) {
229+
r=p;
230+
}else {
231+
mx=nums[p];
232+
}
233+
const q=j-p+i;
234+
if (nums[q]>mi) {
235+
l=q;
236+
}else {
237+
mi=nums[q];
238+
}
239+
}
240+
returnr===-1?0:r-l+1;
241+
};
242+
243+
const ans:number[]= [];
244+
for (let i=0;i<=n-k;++i) {
245+
ans.push(f(i,i+k-1));
246+
}
247+
returnans;
248+
}
98249
```
99250

100251
<!-- tabs:end -->

‎solution/3500-3599/3555.Smallest Subarray to Sort in Every Sliding Window/README_EN.md

Lines changed: 155 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -67,32 +67,183 @@ edit_url: https://github.com/doocs/leetcode/edit/main/solution/3500-3599/3555.Sm
6767

6868
<!-- solution:start-->
6969

70-
###Solution 1
70+
###Solution 1: Enumeration + Maintaining Left Maximum and Right Minimum
71+
72+
We can enumerate every subarray of length $k$. For each subarray $nums[i...i + k - 1]$, we need to find the smallest continuous segment such that, after sorting it, the entire subarray becomes non-decreasing.
73+
74+
For the subarray $nums[i...i + k - 1]$, we can traverse from left to right, maintaining a maximum value $mx$. If the current value is less than $mx$, it means the current value is not in the correct position, so we update the right boundary $r$ to the current position. Similarly, we can traverse from right to left, maintaining a minimum value $mi$. If the current value is greater than $mi$, it means the current value is not in the correct position, so we update the left boundary $l$ to the current position. Initially, both $l$ and $r$ are set to $-1$. If neither $l$ nor $r$ is updated, it means the subarray is already sorted, so we return $0$; otherwise, we return $r - l + 1$.
75+
76+
The time complexity is $O(n \times k)$, where $n$ is the length of the array $\textit{nums}$. The space complexity is $O(1)$.
7177

7278
<!-- tabs:start-->
7379

7480
####Python3
7581

7682
```python
77-
83+
classSolution:
84+
defminSubarraySort(self,nums: List[int],k:int) -> List[int]:
85+
deff(i:int,j:int) ->int:
86+
mi, mx= inf,-inf
87+
l= r=-1
88+
for kinrange(i, j+1):
89+
if mx> nums[k]:
90+
r= k
91+
else:
92+
mx= nums[k]
93+
p= j- k+ i
94+
if mi< nums[p]:
95+
l= p
96+
else:
97+
mi= nums[p]
98+
return0if r==-1else r- l+1
99+
100+
n=len(nums)
101+
return [f(i, i+ k-1)for iinrange(n- k+1)]
78102
```
79103

80104
####Java
81105

82106
```java
83-
107+
classSolution {
108+
privateint[] nums;
109+
privatefinalint inf=1<<30;
110+
111+
publicint[]minSubarraySort(int[]nums,intk) {
112+
this.nums= nums;
113+
int n= nums.length;
114+
int[] ans=newint[n- k+1];
115+
for (int i=0; i< n- k+1;++i) {
116+
ans[i]= f(i, i+ k-1);
117+
}
118+
return ans;
119+
}
120+
121+
privateintf(inti,intj) {
122+
int mi= inf, mx=-inf;
123+
int l=-1, r=-1;
124+
for (int k= i; k<= j;++k) {
125+
if (nums[k]< mx) {
126+
r= k;
127+
}else {
128+
mx= nums[k];
129+
}
130+
int p= j- k+ i;
131+
if (nums[p]> mi) {
132+
l= p;
133+
}else {
134+
mi= nums[p];
135+
}
136+
}
137+
return r==-1?0: r- l+1;
138+
}
139+
}
84140
```
85141

86142
####C++
87143

88144
```cpp
89-
145+
classSolution {
146+
public:
147+
vector<int> minSubarraySort(vector<int>& nums, int k) {
148+
const int inf = 1 << 30;
149+
int n = nums.size();
150+
auto f =[&](int i, int j) -> int {
151+
int mi = inf, mx = -inf;
152+
int l = -1, r = -1;
153+
for (int k = i; k <= j; ++k) {
154+
if (nums[k] < mx) {
155+
r = k;
156+
} else {
157+
mx = nums[k];
158+
}
159+
int p = j - k + i;
160+
if (nums[p] > mi) {
161+
l = p;
162+
} else {
163+
mi = nums[p];
164+
}
165+
}
166+
return r == -1 ? 0 : r - l + 1;
167+
};
168+
vector<int> ans;
169+
for (int i = 0; i < n - k + 1; ++i) {
170+
ans.push_back(f(i, i + k - 1));
171+
}
172+
return ans;
173+
}
174+
};
90175
```
91176
92177
#### Go
93178
94179
```go
180+
func minSubarraySort(nums []int, k int) []int {
181+
const inf = 1 << 30
182+
n := len(nums)
183+
f := func(i, j int) int {
184+
mi := inf
185+
mx := -inf
186+
l, r := -1, -1
187+
for p := i; p <= j; p++ {
188+
if nums[p] < mx {
189+
r = p
190+
} else {
191+
mx = nums[p]
192+
}
193+
q := j - p + i
194+
if nums[q] > mi {
195+
l = q
196+
} else {
197+
mi = nums[q]
198+
}
199+
}
200+
if r == -1 {
201+
return 0
202+
}
203+
return r - l + 1
204+
}
205+
206+
ans := make([]int, 0, n-k+1)
207+
for i := 0; i <= n-k; i++ {
208+
ans = append(ans, f(i, i+k-1))
209+
}
210+
return ans
211+
}
212+
```
95213

214+
####TypeScript
215+
216+
```ts
217+
function minSubarraySort(nums:number[],k:number):number[] {
218+
const inf=Infinity;
219+
const n=nums.length;
220+
const f= (i:number,j:number):number=> {
221+
let mi=inf;
222+
let mx=-inf;
223+
let l=-1,
224+
r=-1;
225+
for (let p=i;p<=j;++p) {
226+
if (nums[p]<mx) {
227+
r=p;
228+
}else {
229+
mx=nums[p];
230+
}
231+
const q=j-p+i;
232+
if (nums[q]>mi) {
233+
l=q;
234+
}else {
235+
mi=nums[q];
236+
}
237+
}
238+
returnr===-1?0:r-l+1;
239+
};
240+
241+
const ans:number[]= [];
242+
for (let i=0;i<=n-k;++i) {
243+
ans.push(f(i,i+k-1));
244+
}
245+
returnans;
246+
}
96247
```
97248

98249
<!-- tabs:end -->

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp