算法技巧-栈

1.栈

例 2：大鱼吃小鱼

【题目】在水中有许多鱼，可以认为这些鱼停放在 x 轴上。再给定两个数组 Size，Dir，Size[i] 表示第 i 条鱼的大小，Dir[i] 表示鱼的方向 （0 表示向左游，1 表示向右游）。这两个数组分别表示鱼的大小和游动的方向，并且两个数组的长度相等。鱼的行为符合以下几个条件:

所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离；

当方向相对时，大鱼会吃掉小鱼；

鱼的大小都不一样。

输入：Size = [4, 2, 5, 3, 1], Dir = [1, 1, 0, 0, 0]

输出：3

int solution(int[] fishSize, int[] fishDirection) {
   

  // 首先拿到鱼的数量

  // 如果鱼的数量小于等于1，那么直接返回鱼的数量

  final int fishNumber = fishSize.length;

  if (fishNumber <= 1) {
   

    return fishNumber;

  }

  // 0表示鱼向左游

  final int left = 0;

  // 1表示鱼向右游

  final int right = 1;

  Stack<Integer> t = new Stack();

  for (int i = 0; i < fishNumber; i++) {
   

    // 当前鱼的情况：1，游动的方向；2，大小

    final int curFishDirection = fishDirection[i];

    final int curFishSize = fishSize[i];

    // 当前的鱼是否被栈中的鱼吃掉了

    boolean hasEat = false;

    // 如果栈中还有鱼，并且栈中鱼向右，当前的鱼向左游，那么就会有相遇的可能性

    while (!t.empty() && fishDirection[t.peek()] == right &&

           curFishDirection == left) {
   

      // 如果栈顶的鱼比较大，那么把新来的吃掉

      if (fishSize[t.peek()] > curFishSize) {
   

        hasEat = true;

        break;

      }

      // 如果栈中的鱼较小，那么会把栈中的鱼吃掉，栈中的鱼被消除，所以需要弹栈。

      t.pop();

    }

    // 如果新来的鱼，没有被吃掉，那么压入栈中。

    if (!hasEat) {
   

      t.push(i);

    }

  }

  return t.size();

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

2、单调栈

2.1 例 3：找出数组中右边比我小的元素

【题目】一个整数数组 A，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。

输入：[5, 2]

输出：[1, -1]

public static int[] findRightSmall(int[] A) {
   

  // 结果数组

  int[] ans = new int[A.length];

  // 注意，栈中的元素记录的是下标

  Stack<Integer> t = new Stack();

  for (int i = 0; i < A
1
2
3
4
5
6
7
8
9
10
11