Skip to content

Commit caf98ab

Browse files
dairongpengdairongpeng
committed
get near less
1 parent 4920329 commit caf98ab

File tree

1 file changed

+109
-150
lines changed

1 file changed

+109
-150
lines changed

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

Lines changed: 109 additions & 150 deletions
Original file line numberDiff line numberDiff line change
@@ -242,9 +242,9 @@ func main() {
242242

243243
1、 数据状况层面是否可以优化
244244

245-
2、 问题本身是否可以优化。单调性，首位指针（头指针往右走，尾指针往左走）等
245+
2、 问题本身是否可以优化。单调性，首尾指针（头指针往右走，尾指针往左走）等
246246

247-
> 遇到一个问题我们先观察，问题本身和范围是否可以建立单调性，至于需要用哪个原型来解决，串口和首位指针法是常见的流程。所以窗口和首位指针主要用来解决单调性的
247+
> 遇到一个问题我们先观察，问题本身和范围是否可以建立单调性，至于需要用哪个原型来解决，窗口和首位指针法是常见的流程。所以窗口和首位指针主要用来解决单调性的
248248
249249
## 1.2 单调栈
250250

@@ -278,182 +278,141 @@ func main() {
278278
> 如果存在相等元素的情况，我们栈中每个元素保存为list表示相等元素列表。无法直接进入单调栈时，弹出list最右侧的元素，该元素右侧最近的比自己小的数，就是迫使它弹出的那个数。该元素左侧最近比它小的数，就是自身的这个list压着的的list的最右的数。list的相同元素有两种情况，一种是两个数相等且挨着，另外一种是某个位置释放了中间位置的数后遇到相等元素，进入一个list中去。画栈模拟可看出
279279
280280

281-
```Java
282-
283-
package class01;
281+
```Go
282+
package main
284283

285-
import java.util.List;
286-
import java.util.ArrayList;
287-
import java.util.Stack;
284+
import "fmt"
288285

289-
public class Code03_MonotonousStack {
286+
// 单调栈
290287

291-
// 数组中没有重复值的情况
292-
public static int[][] getNearLessNoRepeat(int[] arr) {
293-
int[][] res = new int[arr.length][2];
294-
Stack<Integer> stack = new Stack<>();
295-
for (int i = 0; i < arr.length; i++) {
296-
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
297-
int popIndex = stack.pop();
298-
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
299-
res[popIndex][0] = leftLessIndex;
300-
res[popIndex][1] = i;
301-
}
302-
stack.push(i);
303-
}
304-
while (!stack.isEmpty()) {
305-
int popIndex = stack.pop();
306-
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
307-
res[popIndex][0] = leftLessIndex;
308-
res[popIndex][1] = -1;
309-
}
310-
return res;
288+
// 数组中没有重复值的情况
289+
func getNearLessNoRepeat(arr []int) [][]int {
290+
res := make([][]int, len(arr))
291+
for i := 0; i < len(arr); i++ {
292+
res[i] = make([]int, 2)
311293
}
312294

313-
// arr [3, 2, 1, 4, 5]
314-
// 0 1 2 3 4
315-
316-
// 表示 0这个数左边最近比0小的没有，位置是-1，右边1。1位置数左边最近比0小的没有-1，右边2
317-
// [
318-
// 0 : [-1, 1 ]
319-
// 1 : [-1, 2 ]
320-
321-
// ]
322-
// 数组中存在重复值的情况
323-
public static int[][] getNearLess(int[] arr) {
324-
int[][] res = new int[arr.length][2];
325-
326-
327-
// List<Integer> -> 放的是位置，同样值的东西，位置压在一起
328-
// 代表值 底 -> 顶 小 -> 大
329-
Stack<List<Integer>> stack = new Stack<>();
330-
for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈
331-
// 栈底 -> 栈顶， 小 -> 大
332-
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
333-
List<Integer> popIs = stack.pop();
334-
// 取位于下面位置的列表中，最晚加入的那个
335-
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
336-
for (Integer popi : popIs) {
337-
res[popi][0] = leftLessIndex;
338-
res[popi][1] = i;
339-
}
340-
}
341-
// 相等的、比你小的
342-
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
343-
stack.peek().add(Integer.valueOf(i));
295+
// 模拟一个栈
296+
stack := make([]int, 0)
297+
for i := 0; i < len(arr); i++ {
298+
for len(stack) != 0 && arr[stack[len(stack) - 1]] > arr[i] {
299+
// 出栈 stack pop
300+
popIndex := stack[len(stack) - 1]
301+
stack = stack[:len(stack) - 1]
302+
303+
leftLessIndex := 0
304+
if len(stack) == 0 {
305+
leftLessIndex = -1
344306
} else {
345-
ArrayList<Integer> list = new ArrayList<>();
346-
list.add(i);
347-
stack.push(list);
348-
}
349-
}
350-
while (!stack.isEmpty()) {
351-
List<Integer> popIs = stack.pop();
352-
// 取位于下面位置的列表中，最晚加入的那个
353-
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
354-
for (Integer popi : popIs) {
355-
res[popi][0] = leftLessIndex;
356-
res[popi][1] = -1;
307+
leftLessIndex = stack[len(stack) - 1]
357308
}
309+
310+
res[popIndex][0] = leftLessIndex
311+
res[popIndex][1] = i
358312
}
359-
return res;
313+
// stack push i
314+
stack = append(stack, i)
360315
}
361316

362-
// for test
363-
public static int[] getRandomArrayNoRepeat(int size) {
364-
int[] arr = new int[(int) (Math.random() * size) + 1];
365-
for (int i = 0; i < arr.length; i++) {
366-
arr[i] = i;
367-
}
368-
for (int i = 0; i < arr.length; i++) {
369-
int swapIndex = (int) (Math.random() * arr.length);
370-
int tmp = arr[swapIndex];
371-
arr[swapIndex] = arr[i];
372-
arr[i] = tmp;
317+
for len(stack) != 0 {
318+
// 出栈 stack pop
319+
popIndex := stack[len(stack) - 1]
320+
stack = stack[:len(stack) - 1]
321+
322+
leftLessIndex := 0
323+
if len(stack) == 0 {
324+
leftLessIndex = -1
325+
} else {
326+
// leftLessIndex = stack peek
327+
leftLessIndex = stack[len(stack) - 1]
373328
}
374-
return arr;
329+
330+
res[popIndex][0] = leftLessIndex
331+
res[popIndex][1] = -1
375332
}
376333

377-
// for test
378-
public static int[] getRandomArray(int size, int max) {
379-
int[] arr = new int[(int) (Math.random() * size) + 1];
380-
for (int i = 0; i < arr.length; i++) {
381-
arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
382-
}
383-
return arr;
334+
return res
335+
}
336+
337+
// arr [3, 2, 1, 4, 5]
338+
// 0 1 2 3 4
339+
340+
// 表示 0这个数左边最近比0小的没有，位置是-1，右边1。1位置数左边最近比0小的没有-1，右边2
341+
// [
342+
// 0 : [-1, 1 ]
343+
// 1 : [-1, 2 ]
344+
345+
// ]
346+
// 数组中存在重复值的情况
347+
func getNearLess(arr []int) [][]int {
348+
res := make([][]int, len(arr))
349+
for i := 0; i < len(arr); i++ {
350+
res[i] = make([]int, 2)
384351
}
385352

386-
// for test
387-
public static int[][] rightWay(int[] arr) {
388-
int[][] res = new int[arr.length][2];
389-
for (int i = 0; i < arr.length; i++) {
390-
int leftLessIndex = -1;
391-
int rightLessIndex = -1;
392-
int cur = i - 1;
393-
while (cur >= 0) {
394-
if (arr[cur] < arr[i]) {
395-
leftLessIndex = cur;
396-
break;
397-
}
398-
cur--;
399-
}
400-
cur = i + 1;
401-
while (cur < arr.length) {
402-
if (arr[cur] < arr[i]) {
403-
rightLessIndex = cur;
404-
break;
405-
}
406-
cur++;
353+
// []int -> 放的是位置，同样值的东西，位置压在一起
354+
// 代表值 底 -> 顶 小 -> 大
355+
stack := make([][]int, 0)
356+
357+
for i := 0; i < len(arr); i++ { // i -> arr[i] 进栈
358+
// 栈底 -> 栈顶， 小 -> 大
359+
for len(stack) != 0 && arr[stack[len(stack) - 1][0]] > arr[i] {
360+
// 出栈 stack pop
361+
popIs := stack[len(stack) - 1]
362+
stack = stack[:len(stack) - 1]
363+
364+
// 取位于下面位置的列表中，最晚加入的那个
365+
leftLessIndex := 0
366+
if len(stack) == 0 {
367+
leftLessIndex = -1
368+
} else {
369+
leftLessIndex = stack[len(stack) - 1][len(stack[len(stack) - 1]) - 1]
407370
}
408-
res[i][0] = leftLessIndex;
409-
res[i][1] = rightLessIndex;
410-
}
411-
return res;
412-
}
413371

414-
// for test
415-
public static boolean isEqual(int[][] res1, int[][] res2) {
416-
if (res1.length != res2.length) {
417-
return false;
418-
}
419-
for (int i = 0; i < res1.length; i++) {
420-
if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
421-
return false;
372+
for _,popi := range popIs {
373+
res[popi][0] = leftLessIndex
374+
res[popi][1] = i
422375
}
423376
}
424377

425-
return true;
378+
// 相等的、比你小的
379+
if len(stack) != 0 && arr[stack[len(stack) - 1][0]] == arr[i] {
380+
stack[len(stack) - 1] = append(stack[len(stack) - 1], i)
381+
} else {
382+
list := make([]int, 0)
383+
list = append(list, i)
384+
// stack push
385+
stack = append(stack, list)
386+
}
426387
}
427388

428-
// for test
429-
public static void printArray(int[] arr) {
430-
for (int i = 0; i < arr.length; i++) {
431-
System.out.print(arr[i] + " ");
389+
for len(stack) != 0 {
390+
// stack pop
391+
popIs := stack[len(stack) - 1]
392+
stack = stack[:len(stack) - 1]
393+
394+
// 取位于下面位置的列表中，最晚加入的那个
395+
leftLessIndex := 0
396+
if len(stack) == 0 {
397+
leftLessIndex = -1
398+
} else {
399+
leftLessIndex = stack[len(stack) - 1][len(stack[len(stack) - 1]) - 1]
432400
}
433-
System.out.println();
434-
}
435401

436-
public static void main(String[] args) {
437-
int size = 10;
438-
int max = 20;
439-
int testTimes = 2000000;
440-
for (int i = 0; i < testTimes; i++) {
441-
int[] arr1 = getRandomArrayNoRepeat(size);
442-
int[] arr2 = getRandomArray(size, max);
443-
if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
444-
System.out.println("Oops!");
445-
printArray(arr1);
446-
break;
447-
}
448-
if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
449-
System.out.println("Oops!");
450-
printArray(arr2);
451-
break;
452-
}
402+
for _,popi := range popIs {
403+
res[popi][0] = leftLessIndex
404+
res[popi][1] = -1
453405
}
454406
}
407+
return res
455408
}
456409

410+
func main() {
411+
arr := []int{4, 3, 5, 6, 7}
412+
fmt.Println(getNearLessNoRepeat(arr))
413+
arr = []int{4, 3, 5, 4, 3, 3, 6, 7}
414+
fmt.Println(getNearLess(arr))
415+
}
457416
```
458417

459418
### 1.2.2 单调栈的应用

0 commit comments

Comments
 (0)