Skip to content

Commit 4920329

Browse files
dairongpengdairongpeng
committed
sub arr num
1 parent e4b82a7 commit 4920329

File tree

1 file changed

+88
-79
lines changed

1 file changed

+88
-79
lines changed

‎13-《进阶》单调栈和窗口.md

Lines changed: 88 additions & 79 deletions
Original file line numberDiff line numberDiff line change
@@ -120,111 +120,120 @@ func main() {
120120

121121
### 1.1.5 高频题二：达标子数组数量问题
122122

123-
给定一个整形数组arr，和衣蛾整数num。某个arr中的子数组sub，如果想达标，必须满足:sub中最大值-sub中最小值<=num，返回arr中达标子数组的数量
123+
给定一个整形数组arr，和一个整数num。某个arr中的子数组sub，如果想达标，必须满足: sub中最大值-sub中最小值<=num，返回arr中达标子数组的数量
124124

125125
> 子数组是连续的
126126
127-
> 结论1：对于[L...R]范围达标，那么[L...R]上的子数组都达标。max[L...R]肯定比其子数组的max要大，min[L...R]肯定比其范围内的子数组要小，那么[L...R]上满足max - min < num，则其子数组必定满足
127+
> 结论1：对于[L,R]范围达标，那么[L,R]上的子数组都达标。max[L...R]肯定比其子数组的max要大，min[L...R]肯定比其范围内的子数组要小，那么[L...R]上满足max - min < num，则其子数组必定满足
128128
129129
> 同理可得结论2：对于[L...R]范围不达标，那么扩展范围后的[L'...R']也不达标
130130
131131
> 我们建立两个双端队列，一个是窗口最大值的双端队列，一个是窗口最小值的双端队列。我们扩展我们的窗口R加1，每扩展一个判断是否仍然达标，达标继续扩展，不达标就停，可以得到本次子数组的达标情况，接着缩小我们的窗口L加1，继续...。窗口滑动不会回退，整体O(N)
132132
133-
```Java
134-
package class01;
133+
```Go
134+
package main
135135

136-
import java.util.LinkedList;
136+
import (
137+
"container/list"
138+
"fmt"
139+
)
137140

138-
public class Code02_AllLessNumSubArray {
141+
// 达标子数组数量问题
139142

140-
public static int getNum(int[] arr, int num) {
141-
if (arr == null || arr.length == 0) {
142-
return 0;
143-
}
144-
// 窗口内最小值的更新结构
145-
LinkedList<Integer> qmin = new LinkedList<Integer>();
146-
// 窗口内的最大值的更新结构
147-
LinkedList<Integer> qmax = new LinkedList<Integer>();
148-
int L = 0;
149-
int R = 0;
150-
// [L..R) -> [0,0) 窗口内无数 [1,1)
151-
// [0,1) -> [0~0] 窗口里只有一个数
152-
int res = 0;
153-
// L是开头位置，尝试每一个开头
154-
while (L < arr.length) {
155-
156-
// 如果此时窗口的开头是L,下面的while工作是:R向右扩到违规为止
157-
158-
// R是最后一个达标位置的再下一个，通过下文的break终止
159-
while (R < arr.length) {
160-
// R位置的数进入窗口后，最小值的更新结构和最大值的更新结构都要更新
161-
while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]) {
162-
qmin.pollLast();
163-
}
164-
qmin.addLast(R);
165-
// R -> arr[R],
166-
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
167-
qmax.pollLast();
168-
}
169-
qmax.addLast(R);
143+
// getNum 给定样本数组，和一个目标数值num。求arr中达标的子数组，达标的要求为子数组中最大值减去子数组中最小值小于等于num
144+
func getNum(arr []int, num int) int {
145+
if len(arr) == 0 {
146+
return 0
147+
}
170148

171-
// 如果此时不满足了，break。说明窗口已经成长到了第一个不达标的数进来了
172-
if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
173-
break;
149+
// 窗口内最小值的更新结构
150+
qmin := list.List{}
151+
// 窗口内的最大值的更新结构
152+
qmax := list.List{}
153+
154+
// 最小值双端队列的头部元素
155+
var minfe = &list.Element{}
156+
// 最小值双端队列的尾部元素
157+
var minee = &list.Element{}
158+
159+
// 最大值双端队列的头部元素
160+
var maxfe = &list.Element{}
161+
// 最小值双端队列的尾部元素
162+
var maxee = &list.Element{}
163+
164+
L := 0
165+
R := 0
166+
// [L..R) -> [0,0) 窗口内无数 [1,1)
167+
// [0,1) -> [0~0] 窗口里只有一个数
168+
res := 0
169+
// L是开头位置，尝试每一个开头
170+
for L < len(arr) {
171+
// 如果此时窗口的开头是L,下面的for工作是:R向右扩到违规为止
172+
173+
// R是最后一个达标位置的再下一个，通过下文的break终止
174+
for R < len(arr) {
175+
// R位置的数进入窗口后，最小值的更新结构和最大值的更新结构都要更新
176+
for qmin.Len() != 0 && arr[qmin.Back().Value.(int)] >= arr[R] {
177+
// 尾部移除
178+
qmin.Remove(minee)
179+
if qmin.Len() > 0 {
180+
minfe = qmin.Front()
181+
minee = qmin.Back()
174182
}
175-
R++;
176183
}
177184

178-
// R是最后一个达标位置的再下一个，第一个违规的位置
179-
res += R - L;
180-
181-
// 检查最小值和最大值的更新结构有没有过期
182-
if (qmin.peekFirst() == L) {
183-
qmin.pollFirst();
184-
}
185-
if (qmax.peekFirst() == L) {
186-
qmax.pollFirst();
185+
qmin.PushBack(R)
186+
minee = qmin.Back()
187+
minfe = qmin.Front()
188+
189+
// R -> arr[R],
190+
for qmax.Len() != 0 && arr[qmax.Back().Value.(int)] <= arr[R] {
191+
// 尾部移除
192+
qmax.Remove(maxee)
193+
if qmax.Len() > 0 {
194+
maxfe = qmax.Front()
195+
maxee = qmax.Back()
196+
}
187197
}
188198

189-
// 窗口左边界向右滑动，窗口容量此时减1
190-
L++;
191-
192-
}
193-
return res;
194-
}
199+
qmax.PushBack(R)
200+
maxee = qmax.Back()
201+
maxfe = qmax.Front()
195202

196-
// for test
197-
public static int[] getRandomArray(int len) {
198-
if (len < 0) {
199-
return null;
203+
if arr[qmax.Front().Value.(int)]-arr[qmin.Front().Value.(int)] > num {
204+
break
205+
}
206+
R++
200207
}
201-
int[] arr = new int[len];
202-
for (int i = 0; i < len; i++) {
203-
arr[i] = (int) (Math.random() * 10);
208+
// R是最后一个达标位置的再下一个，第一个违规的位置
209+
res += R - L
210+
// 检查最小值和最大值的更新结构有没有过期
211+
if qmin.Front().Value.(int) == L {
212+
qmin.Remove(minfe)
213+
if qmin.Len() > 0 {
214+
minfe = qmin.Front()
215+
minee = qmin.Back()
216+
}
204217
}
205-
return arr;
206-
}
207218

208-
// for test
209-
public static void printArray(int[] arr) {
210-
if (arr != null) {
211-
for (int i = 0; i < arr.length; i++) {
212-
System.out.print(arr[i] + " ");
219+
if qmax.Front().Value.(int) == L {
220+
qmax.Remove(maxfe)
221+
if qmax.Len() > 0 {
222+
maxfe = qmax.Front()
223+
maxee = qmax.Back()
213224
}
214-
System.out.println();
215225
}
226+
// 窗口左边界向右滑动，窗口容量此时减1
227+
L++
216228
}
217-
218-
public static void main(String[] args) {
219-
int[] arr = getRandomArray(30);
220-
int num = 5;
221-
printArray(arr);
222-
System.out.println(getNum(arr, num));
223-
224-
}
225-
229+
return res
226230
}
227231

232+
func main() {
233+
arr := []int{4, 2, 1, 5, 6, 1, 7, 22, 53, 16, 24, 65, 72, 17, 21, 42}
234+
num := 5
235+
fmt.Println(getNum(arr, num))
236+
}
228237
```
229238

230239
> 本题根据窗口滑动建立了单调性，上文的结论

0 commit comments

Comments
 (0)